Submission #873929

#	Time	Username	Problem	Language	Result	Execution time	Memory
873929		noiaint	Curtains (NOI23_curtains)	C++17	100 / 100	781 ms	154564 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;

template<class X, class Y>
bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}

template<class X, class Y>
bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}

template<class X, class Y>
bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}

struct node {
    int L, R, M, val;
    int lazy = 0;
    node *l, *r;
    
    node (int _L, int _R) : L(_L), R(_R) {
        M = (L + R) >> 1;
        val = 0;
        if (L < R) {
            l = new node(L, M);
            r = new node(M + 1, R);
        }
    }

    void down() {
        l->lazy = max(l->lazy, lazy);
        r->lazy = max(r->lazy, lazy);
        l->val = max(l->val, lazy);
        r->val = max(r->val, lazy);
    }

    void update(int u, int v, int c) {
        if (v < L || u > R) return;
        if (u <= L && R <= v) {
            lazy = max(lazy, c);
            val = max(val, c);
            return;
        }

        down();

        l->update(u, v, c);
        r->update(u, v, c);

        val = min(l->val, r->val);
    }

    int get(int u, int v) {
        if (v < L || u > R)
            return inf;
        if (u <= L && R <= v) 
            return val;

        down();

        return min(l->get(u, v), r->get(u, v));
    }
} *root;

struct SegmentTree {
    int n;
    vector<int> val, lazy;

    void init(int _n) {
        n = _n;
        val.assign(n * 4 + 5, 0);
        lazy.assign(n * 4 + 5, 0);
    }

    void down(int i) {
        for (int j = i * 2; j <= i * 2 + 1; ++j) {
            val[j] = max(val[j], lazy[i]);
            lazy[j] = max(lazy[j], lazy[i]);
        }
    }

    void update(int i, int L, int R, int l, int r, int c) {
        if (r < L || l > R)
            return;
        if (l <= L && R <= r) {
            val[i] = max(val[i], c);
            lazy[i] = max(lazy[i], c);
            return;
        }

        down(i);

        int M = (L + R) >> 1;
        update(i << 1, L, M, l, r, c);
        update(i << 1 | 1, M + 1, R, l, r, c);
        val[i] = min(val[i << 1], val[i << 1 | 1]);
    }

    int get(int i, int L, int R, int l, int r) {
        if (r < L || l > R)
            return inf;
        if (l <= L && R <= r) 
            return val[i];

        down(i);

        int M = (L + R) >> 1;
        return min(get(i << 1, L, M, l, r),
                   get(i << 1 | 1, M + 1, R, l, r));
    }

    void update(int l, int r, int c) {
        update(1, 1, n, l, r, c);
    }
    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
} t;


int n, m, q;
vector<int> curtain[N];
vector<pair<int, int> > query[N];
int ans[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) {
        int l, r;
        cin >> l >> r;
        curtain[r].push_back(l);
    }

    for (int i = 1; i <= q; ++i) {
        int s, e;
        cin >> s >> e;
        query[e].emplace_back(s, i);
    }

    t.init(n);
    root = new node(1, n);

    for (int r = 1; r <= n; ++ r) {
        for (int l : curtain[r]) {
            // root->update(l, r, l);
            t.update(l, r, l);
        }

        for (auto [l, id] : query[r]) {
            // ans[id] = root->get(l, r) >= l;
            ans[id] = t.get(l, r) >= l;
        }
    }

    for (int i = 1; i <= q; ++i)
        cout << (ans[i] ? "YES" : "NO") << '\n';

    // for (int i = 1; i <= n; ++i)
    //     cout << root->get(i, i) << ' ';

    return 0;
}

/*

*/

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