50分RE求助
查看原帖
50分RE求助
107468
hulean楼主2020/12/2 19:54
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
struct Node {
    int x, y;
} a[N];
int tim[N];
int n, m;
int st[N][21];
map <int, int> mp;
inline int read () {
    int tot = 0, f = 1; char c = getchar ();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar (); }
    while (c >= '0' && c <= '9') { tot = tot * 10 + c - '0'; c = getchar (); }
    return tot * f;
}
inline int query (int l, int r) {
    int len = log(r - l + 1) / log (2);
    return max (st[l][len], st[r - (1 << len) + 1][len]);
}
signed main () {
    n = read ();
    for (int i = 1; i <= n; i++) {
        a[i].x = read (); a[i].y = read ();
        tim[i] = a[i].x;
        mp[tim[i]] = i;
        st[i][0] = a[i].y;
    }
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i+(1<<j)-1 <= n; i++) {
            st[i][j] = max (st[i + (1 << (j - 1))][j - 1], st[i][j - 1]);
        }
    m = read ();
    while (m--) {
        int x = read (), y = read ();
        int fy = lower_bound (tim + 1, tim + 1 + n, y) - tim, ty = *lower_bound (tim + 1, tim + 1 + n, y);
        int fx = lower_bound (tim + 1, tim + 1 + n, x) - tim, tx = *lower_bound (tim + 1, tim + 1 + n, x);
        // cout<<fx<<" "<<tx<<" "<<fy<<" "<<ty<<endl;
        if (ty == y) fy--; if (tx == x) fx++;
        int in = query (fx, fy);
        if (ty == y) fy++; if (tx == x) fx--;
        // cout<<in<<" "<<a[fx].y<<" "<<a[fy].y<<endl;
        if (ty != y) {
            if (tx != x) puts ("maybe");
            else {
                if (a[fx].y > in) puts ("maybe");
                else puts ("false");
            }
        }
        else {
            if (tx == x) {
                if (a[fx].y < a[fy].y) puts ("false");
                else if (in >= a[fy].y) puts ("false");
                else if (y - x == mp[y] - mp[x]) puts ("true");
                else puts ("maybe");
            }
            else {
                if (a[fy].y <= in) puts ("false");
                else puts ("maybe");
            }
        }
    }
    return 0;
}

2020/12/2 19:54
加载中...