萌新刚学线段树,求助
查看原帖
萌新刚学线段树,求助
86973
花园Serena楼主2020/12/1 19:47

不知道为什么第一个点会MLE,求大佬解答

#include <bits/stdc++.h>
using namespace std;
#define R register int
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid (x + y >> 1)
#define low(x) lower_bound(year + 1, year + n + 1, x) - year
const int N = 5e4 + 1;
int year[N], rain[N], t[N << 2], n, m;
void inline update (int i) {
    t[i] = max(t[ls], t[rs]);
}
void built (int i, int x, int y) {
    if(x == y) {t[i] = rain[x]; return;}
    built(ls, x, mid); built(rs, mid + 1, y);
    update(i);  return ;
}
int Ans (int i, int x, int y, int l, int r) {
    if(x >= l && y <= r) return t[i];
    int ans = -0x7fffffff;
    if(l <= mid) ans = max(ans, Ans(ls, x, mid, l, r));
    if(r > mid) ans = max(ans, Ans(rs, mid + 1, y, l, r));
    return ans;
}
int main ()  {
    scanf("%d", &n);
    for(R i = 1; i <= n; i ++)
        scanf("%d%d", &year[i], &rain[i]);
    scanf("%d", &m); built(1, 1, n);
    for(R i = 1; i <= m; i ++) {
        int x, y, l, r, wuhu;
        bool st = false, ed = false;
        scanf("%d%d", &x ,&y);
        l = low(x); r = low(y); wuhu = l;
        if(x != year[l]) st = true;
        else wuhu ++;
        if(year[r] != y) ed = true;
        int ans = Ans (1, 1, n, wuhu, r - 1);
        if(!st && ans >= rain[l]) printf("false\n");
        else if(!ed && ans >= rain[r]) printf("false\n");
        else if(!ed && !st && rain[l] <= rain[r]) printf("false\n");
        else if((r - l != y - x) || st || ed) printf("maybe\n");
        else printf("true\n");
    }
    return 0;
}
2020/12/1 19:47
加载中...