제출 #1331537

#제출 시각아이디문제언어결과실행 시간메모리
1331537xorreverseCurtains (NOI23_curtains)C++20
100 / 100
972 ms114016 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxN = 5e5 + 5;
int n, m, q;
pair<int, int> a[maxN];
pair<int, int> g[maxN];

vector<pair<int, int>> ps[maxN];
vector<int> d[maxN];
vector<int> h[maxN];
vector<array<int, 3>> ans[maxN];
int mx[4 * maxN];
int lmao[maxN];
bool vis[maxN];
void up(int x, int l, int r, int u, int chg){
    if (l > r || l > u || r < u) return;
    if (l == r){
        mx[x] = max(mx[x], chg);
        return;
    }
    int mid = (l + r) / 2;
    up(x * 2, l, mid, u, chg);
    up(x * 2 + 1, mid + 1, r, u, chg);
    mx[x] = max(mx[x * 2], mx[x * 2 + 1]);
}

int re(int x, int l, int r, int u, int v){
    if (l > r || l > v || r < u) return 0;
    if (l >= u&& r <= v){
        return mx[x];
    }
    int mid = (l + r) / 2;
    return max(re(x * 2, l, mid, u, v), re(x * 2 + 1, mid + 1, r, u, v));
}
void build(int x, int l, int r){
    if (l > r) return;
    if (l == r){
        bool ok = 0;
        for (auto e : d[l]){
            if (e == l){
                ok = 1;
            }
        }
        for (auto k : ps[l]){
            if (k.first == l){
                vis[k.second] = ok;
            }
        }
        return;

    }
    int mid = (l + r) /2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    vector<pair<int, int>> cur;
    for (int i = l; i <= r; i ++) ans[i].clear();
    for (int i = mid; i >= l; i --){
        int mx = i - 1;

        for (auto j : d[i]){
            if (j >  mid) continue;
            mx = max(mx, j);
            while (!cur.empty()){

                pair<int, int> h = cur.back();
                if (i <= h.first && j >= h.first - 1){
                    mx = max(mx, j);
                    mx = max(mx, h.second);
                    cur.pop_back();
                }
                else{
                    break;
                }
            }
            cur.push_back({i, mx});
        }
                for (auto k : ps[i]){
                    if (k.first > mid && k.first <= r){
                    //    if (k.second == 4) cout << "he " << l << " " << r << " " << i << " " << mx << '\n';
                        ans[k.first].push_back({k.second, i, mx});
                    }
                }

    }
    cur.clear();
    cur.shrink_to_fit();
    lmao[mid + 1] = -1e9;
    for (int i = mid + 1; i <= r; i ++){
        for (auto j : h[i]){
            if (j <= mid && j >= l){
                up(1, 1, n, j, i);
          //  if (l == 1&& r == 10) cout << "wtf " << j << " " << i << '\n';
            }
            else if (j == mid + 1){
                lmao[j] = max(lmao[j], i);
            }
        }
        int mx = i + 1;
        for (auto j : h[i]){
            if (j <= mid) continue;
            //if (l == 1 && r == 10) cout << i << " " << cur.size() << '\n';
            mx = min(mx, j);
            while (!cur.empty()){
                pair<int, int> h = cur.back();
                if (j <= h.second + 1 && i >= h.second){
                    mx = min(mx, j);
                    mx = min(mx, h.first);
                    cur.pop_back();
                }
                else{
                    break;
                }
            }
            cur.push_back({mx, i});

        }
        for (auto j : ans[i]){
            int val = -1e9;
            if (j[2] + 1 == mid + 1) val = max(re(1, 1, n, j[1], mid), lmao[mid + 1]);
            else{
                val = max(re(1, 1, n, j[1], j[2] + 1), val);
               // if (j[0] == 4) cout << val << " " <<  << '\n';
            }
            if (val <= mid) continue;
         //   if (j[0] == 3) cout << i << " " << l << " " << r << '\n';
            val = re(1, 1, n, j[1], mid);
            val = max(val, lmao[mid + 1]);
            if (val >= mx - 1) vis[j[0]] = 1;
        }

    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i ++){
        cin >> a[i].first >> a[i].second;
        d[a[i].first].push_back(a[i].second);
        h[a[i].second].push_back(a[i].first);
    }
    for (int i = 1; i <= q; i ++){
        cin >> g[i].first >> g[i].second;
        ps[g[i].first].push_back({g[i].second, i});
    }

    for (int i = 1; i <= n; i ++){
        sort(h[i].begin(), h[i].end());
        sort(ps[i].begin(), ps[i].end());
        sort(d[i].begin(), d[i].end());
    }
    build(1, 1, n);
    for (int i = 1; i <= q; i ++){
        if (vis[i]) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...