oj.uz

Submission #873929

# Submission time Handle Problem Language Result Execution time Memory
873929 2023-11-16T02:48:47 Z noiaint Curtains (NOI23_curtains) C++17
100 / 100
 781 ms 154564 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48988 KB Output is correct
2 Correct 16 ms 48988 KB Output is correct
3 Correct 15 ms 48984 KB Output is correct
4 Correct 19 ms 48988 KB Output is correct
5 Correct 12 ms 48984 KB Output is correct
6 Correct 15 ms 48984 KB Output is correct
7 Correct 17 ms 48988 KB Output is correct
8 Correct 14 ms 48988 KB Output is correct
9 Correct 11 ms 49164 KB Output is correct
10 Correct 16 ms 49096 KB Output is correct
11 Correct 14 ms 48988 KB Output is correct
12 Correct 14 ms 49048 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48988 KB Output is correct
2 Correct 16 ms 48988 KB Output is correct
3 Correct 15 ms 48984 KB Output is correct
4 Correct 19 ms 48988 KB Output is correct
5 Correct 12 ms 48984 KB Output is correct
6 Correct 15 ms 48984 KB Output is correct
7 Correct 17 ms 48988 KB Output is correct
8 Correct 14 ms 48988 KB Output is correct
9 Correct 11 ms 49164 KB Output is correct
10 Correct 16 ms 49096 KB Output is correct
11 Correct 14 ms 48988 KB Output is correct
12 Correct 14 ms 49048 KB Output is correct
13 Correct 19 ms 49496 KB Output is correct
14 Correct 13 ms 49364 KB Output is correct
15 Correct 19 ms 49500 KB Output is correct
16 Correct 17 ms 49500 KB Output is correct
17 Correct 16 ms 49500 KB Output is correct
18 Correct 13 ms 49496 KB Output is correct
19 Correct 17 ms 49520 KB Output is correct
20 Correct 16 ms 49520 KB Output is correct
21 Correct 16 ms 49356 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48988 KB Output is correct
2 Correct 16 ms 48988 KB Output is correct
3 Correct 15 ms 48984 KB Output is correct
4 Correct 19 ms 48988 KB Output is correct
5 Correct 12 ms 48984 KB Output is correct
6 Correct 15 ms 48984 KB Output is correct
7 Correct 17 ms 48988 KB Output is correct
8 Correct 14 ms 48988 KB Output is correct
9 Correct 11 ms 49164 KB Output is correct
10 Correct 16 ms 49096 KB Output is correct
11 Correct 14 ms 48988 KB Output is correct
12 Correct 14 ms 49048 KB Output is correct
13 Correct 19 ms 49496 KB Output is correct
14 Correct 13 ms 49364 KB Output is correct
15 Correct 19 ms 49500 KB Output is correct
16 Correct 17 ms 49500 KB Output is correct
17 Correct 16 ms 49500 KB Output is correct
18 Correct 13 ms 49496 KB Output is correct
19 Correct 17 ms 49520 KB Output is correct
20 Correct 16 ms 49520 KB Output is correct
21 Correct 16 ms 49356 KB Output is correct
22 Correct 169 ms 63476 KB Output is correct
23 Correct 173 ms 63736 KB Output is correct
24 Correct 195 ms 65276 KB Output is correct
25 Correct 340 ms 71124 KB Output is correct
26 Correct 158 ms 63568 KB Output is correct
27 Correct 325 ms 71252 KB Output is correct
28 Correct 318 ms 71028 KB Output is correct
29 Correct 155 ms 62732 KB Output is correct
30 Correct 108 ms 62804 KB Output is correct
31 Correct 125 ms 63428 KB Output is correct
32 Correct 281 ms 70204 KB Output is correct
33 Correct 111 ms 62800 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 48988 KB Output is correct
2 Correct 11 ms 49172 KB Output is correct
3 Correct 12 ms 48984 KB Output is correct
4 Correct 11 ms 49084 KB Output is correct
5 Correct 12 ms 49500 KB Output is correct
6 Correct 13 ms 49448 KB Output is correct
7 Correct 12 ms 49524 KB Output is correct
8 Correct 110 ms 62684 KB Output is correct
9 Correct 124 ms 63380 KB Output is correct
10 Correct 284 ms 70060 KB Output is correct
11 Correct 110 ms 62800 KB Output is correct
12 Correct 117 ms 70996 KB Output is correct
13 Correct 129 ms 70960 KB Output is correct
14 Correct 103 ms 71136 KB Output is correct
15 Correct 96 ms 70648 KB Output is correct
16 Correct 97 ms 70996 KB Output is correct
17 Correct 103 ms 70996 KB Output is correct
18 Correct 768 ms 150612 KB Output is correct
19 Correct 737 ms 151120 KB Output is correct
20 Correct 582 ms 151640 KB Output is correct
21 Correct 570 ms 151116 KB Output is correct
22 Correct 564 ms 150096 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48988 KB Output is correct
2 Correct 16 ms 48988 KB Output is correct
3 Correct 15 ms 48984 KB Output is correct
4 Correct 19 ms 48988 KB Output is correct
5 Correct 12 ms 48984 KB Output is correct
6 Correct 15 ms 48984 KB Output is correct
7 Correct 17 ms 48988 KB Output is correct
8 Correct 14 ms 48988 KB Output is correct
9 Correct 11 ms 49164 KB Output is correct
10 Correct 16 ms 49096 KB Output is correct
11 Correct 14 ms 48988 KB Output is correct
12 Correct 14 ms 49048 KB Output is correct
13 Correct 19 ms 49496 KB Output is correct
14 Correct 13 ms 49364 KB Output is correct
15 Correct 19 ms 49500 KB Output is correct
16 Correct 17 ms 49500 KB Output is correct
17 Correct 16 ms 49500 KB Output is correct
18 Correct 13 ms 49496 KB Output is correct
19 Correct 17 ms 49520 KB Output is correct
20 Correct 16 ms 49520 KB Output is correct
21 Correct 16 ms 49356 KB Output is correct
22 Correct 99 ms 56836 KB Output is correct
23 Correct 93 ms 56760 KB Output is correct
24 Correct 135 ms 70224 KB Output is correct
25 Correct 136 ms 70008 KB Output is correct
26 Correct 111 ms 71504 KB Output is correct
27 Correct 116 ms 71508 KB Output is correct
28 Correct 93 ms 69328 KB Output is correct
29 Correct 107 ms 70992 KB Output is correct
30 Correct 133 ms 70224 KB Output is correct
31 Correct 132 ms 70220 KB Output is correct
32 Correct 121 ms 70624 KB Output is correct
33 Correct 115 ms 70912 KB Output is correct
34 Correct 123 ms 69716 KB Output is correct
35 Correct 131 ms 70032 KB Output is correct
36 Correct 119 ms 70480 KB Output is correct
37 Correct 118 ms 70996 KB Output is correct
38 Correct 121 ms 71236 KB Output is correct
39 Correct 97 ms 71012 KB Output is correct
40 Correct 96 ms 70724 KB Output is correct
41 Correct 110 ms 71108 KB Output is correct
42 Correct 94 ms 70520 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48988 KB Output is correct
2 Correct 16 ms 48988 KB Output is correct
3 Correct 15 ms 48984 KB Output is correct
4 Correct 19 ms 48988 KB Output is correct
5 Correct 12 ms 48984 KB Output is correct
6 Correct 15 ms 48984 KB Output is correct
7 Correct 17 ms 48988 KB Output is correct
8 Correct 14 ms 48988 KB Output is correct
9 Correct 11 ms 49164 KB Output is correct
10 Correct 16 ms 49096 KB Output is correct
11 Correct 14 ms 48988 KB Output is correct
12 Correct 14 ms 49048 KB Output is correct
13 Correct 19 ms 49496 KB Output is correct
14 Correct 13 ms 49364 KB Output is correct
15 Correct 19 ms 49500 KB Output is correct
16 Correct 17 ms 49500 KB Output is correct
17 Correct 16 ms 49500 KB Output is correct
18 Correct 13 ms 49496 KB Output is correct
19 Correct 17 ms 49520 KB Output is correct
20 Correct 16 ms 49520 KB Output is correct
21 Correct 16 ms 49356 KB Output is correct
22 Correct 169 ms 63476 KB Output is correct
23 Correct 173 ms 63736 KB Output is correct
24 Correct 195 ms 65276 KB Output is correct
25 Correct 340 ms 71124 KB Output is correct
26 Correct 158 ms 63568 KB Output is correct
27 Correct 325 ms 71252 KB Output is correct
28 Correct 318 ms 71028 KB Output is correct
29 Correct 155 ms 62732 KB Output is correct
30 Correct 108 ms 62804 KB Output is correct
31 Correct 125 ms 63428 KB Output is correct
32 Correct 281 ms 70204 KB Output is correct
33 Correct 111 ms 62800 KB Output is correct
34 Correct 11 ms 48988 KB Output is correct
35 Correct 11 ms 49172 KB Output is correct
36 Correct 12 ms 48984 KB Output is correct
37 Correct 11 ms 49084 KB Output is correct
38 Correct 12 ms 49500 KB Output is correct
39 Correct 13 ms 49448 KB Output is correct
40 Correct 12 ms 49524 KB Output is correct
41 Correct 110 ms 62684 KB Output is correct
42 Correct 124 ms 63380 KB Output is correct
43 Correct 284 ms 70060 KB Output is correct
44 Correct 110 ms 62800 KB Output is correct
45 Correct 117 ms 70996 KB Output is correct
46 Correct 129 ms 70960 KB Output is correct
47 Correct 103 ms 71136 KB Output is correct
48 Correct 96 ms 70648 KB Output is correct
49 Correct 97 ms 70996 KB Output is correct
50 Correct 103 ms 70996 KB Output is correct
51 Correct 768 ms 150612 KB Output is correct
52 Correct 737 ms 151120 KB Output is correct
53 Correct 582 ms 151640 KB Output is correct
54 Correct 570 ms 151116 KB Output is correct
55 Correct 564 ms 150096 KB Output is correct
56 Correct 99 ms 56836 KB Output is correct
57 Correct 93 ms 56760 KB Output is correct
58 Correct 135 ms 70224 KB Output is correct
59 Correct 136 ms 70008 KB Output is correct
60 Correct 111 ms 71504 KB Output is correct
61 Correct 116 ms 71508 KB Output is correct
62 Correct 93 ms 69328 KB Output is correct
63 Correct 107 ms 70992 KB Output is correct
64 Correct 133 ms 70224 KB Output is correct
65 Correct 132 ms 70220 KB Output is correct
66 Correct 121 ms 70624 KB Output is correct
67 Correct 115 ms 70912 KB Output is correct
68 Correct 123 ms 69716 KB Output is correct
69 Correct 131 ms 70032 KB Output is correct
70 Correct 119 ms 70480 KB Output is correct
71 Correct 118 ms 70996 KB Output is correct
72 Correct 121 ms 71236 KB Output is correct
73 Correct 97 ms 71012 KB Output is correct
74 Correct 96 ms 70724 KB Output is correct
75 Correct 110 ms 71108 KB Output is correct
76 Correct 94 ms 70520 KB Output is correct
77 Correct 773 ms 147612 KB Output is correct
78 Correct 775 ms 147612 KB Output is correct
79 Correct 657 ms 154320 KB Output is correct
80 Correct 678 ms 154564 KB Output is correct
81 Correct 639 ms 151968 KB Output is correct
82 Correct 660 ms 153408 KB Output is correct
83 Correct 779 ms 147796 KB Output is correct
84 Correct 781 ms 147628 KB Output is correct
85 Correct 733 ms 149196 KB Output is correct
86 Correct 706 ms 146004 KB Output is correct
87 Correct 737 ms 145516 KB Output is correct
88 Correct 674 ms 152164 KB Output is correct