Submission #1165172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165172		kidkids	Curtains (NOI23_curtains)	C++20	20 / 100	814 ms	28132 KiB

curtains

#include <bits/stdc++.h>

using namespace std;
#define x21 2*x+1
#define x2 2*x

typedef pair<int, int> pii;

const int sz = 500100;
const int maxn = sz * 4 + 100;

struct SegTree {
    int seg[maxn] = {};
    int lazy[maxn] = {};
    void push(int x, int tl, int tr) {
        if (lazy[x] == 0)
            return;
        int m = (tl + tr) / 2;
        seg[2 * x] = max(seg[2 * x], lazy[x]);
        if (seg[2 * x] > tl)
            seg[2 * x] = tl;
            
        seg[2 * x + 1] = max(seg[2 * x + 1], lazy[x]);
        if (seg[2 * x + 1] > m + 1)
            seg[2 * x + 1] = m + 1;

        lazy[2 * x + 1] = max(lazy[2 * x + 1], lazy[x]);
        lazy[2 * x] = max(lazy[2 * x + 1], lazy[x]);
        lazy[x] = 0;
    }
    void add(int v, int l, int r, int x, int tl, int tr) {
        if (l > r || l > tr || tl > r) {
            return;
        }
        // cout<<l<<' '<<r<<' '<<tl<<' '<<tr<<' '<<x<<'\n';
        if (l == tl && r == tr) {
            lazy[x] = max(v, lazy[x]);
            seg[x] = max(v, seg[x]);
            if (seg[x] > tl)
                seg[x] = tl;
            // cout<<'a';
            return;
        }
        push(x,tl,tr);
        int m = (tl + tr) / 2;
        add(v, l, min(r, m), x2, tl, m);
        add(v, max(l, m + 1), r, x21, m + 1, tr);
        seg[x] = min(seg[x2], seg[x21]);
        if (seg[x] > tl)
            seg[x] = tl;
    }
    void add(int v, int l, int r) {
        add(v, l, r, 1, 0, sz - 1);
    }
    int query(int l, int r, int x, int tl, int tr) {
        if (l > r || l > tr || tl > r) {
            return 1e7;
        }
        if (l == tl && r == tr) {
            // cout<<'a'<<seg[x]<<'a';
            return seg[x];
        }
        // cout<<l<<' '<<r<<' '<<tl<<' '<<tr<<' '<<seg[x]<<'\n';
        push(x,tl,tr);

        int m = (tl + tr) / 2;
        return min(
            query(l, min(r, m), x2, tl, m),
            query(max(l, m + 1), r, x21, m + 1, tr));
    }
    int query(int l, int r) {
        return query(l, r, 1, 0, sz - 1);
    }
};

bool comp(pii a, pii b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}
bool comp1(pair<pii, int> a, pair<pii, int> b) {
    if (a.first.second == b.first.second)
        return a.first.first < b.first.first;
    return a.first.second < b.first.second;
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    pii p[b + 10];
    for (int i = 0;i < b;i++) {
        cin >> p[i].first >> p[i].second;
    }
    SegTree seg;
    sort(p, p + b, comp);
    // for (int i = 0;i < b;i++) {
    //     cout << p[i].first << ' ' << p[i].second << '\n';
    //     seg.add(p[i].first, p[i].first, p[i].second);
    //     for (int i = 1;i < a+5;i++) {
    //         cout << seg.query(i, i) << ' ';
    //     }
    //     cout << '\n';
    // }

    pair<pii, int> qq[c + 10];
    for (int i = 0;i < c;i++) {
        cin >> qq[i].first.first >> qq[i].first.second;
        qq[i].second = i;
    }
    sort(qq, qq + c, comp1);
    bool ans[c+10];
    int j = 0;
    for (int i = 0;i < c;i++) {
        while(j!=b&&p[j].second<=qq[i].first.second){
            seg.add(p[j].first, p[j].first, p[j].second);
            j++;
        }
        int l =qq[i].first.first,r = qq[i].first.second;
        ans[qq[i].second] = (seg.query(l,r)==l ? 1 : 0);
        // cout << qq[i].first.first << ' ' << qq[i].first.second << ' ' <<  seg.query(l,r) << ' '<< j <<'\n';
    }
    for(int i = 0;i<c;i++){
        cout<<(ans[i] ? "YES\n" : "NO\n");
    }
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20