oj.uz

Submission #1016421

# Submission time Handle Problem Language Result Execution time Memory
1016421 2024-07-08T05:02:38 Z fryingduc Curtains (NOI23_curtains) C++17
100 / 100
 703 ms 73040 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 5e5 + 5;

int tree[maxn * 4];
int lazy[maxn * 4];
vector<int> segment[maxn];
vector<pair<int, int>> que[maxn];
int n, m, q;
bool ans[maxn];

struct segment_tree {
    int n;
    segment_tree() {}
    segment_tree(int n) : n(n) {}
    void down(int ind, int l, int r) {
        tree[ind] = max(tree[ind], lazy[ind]);
        if(l != r) {
            lazy[ind * 2] = max(lazy[ind * 2], lazy[ind]);
            lazy[ind * 2 + 1] = max(lazy[ind * 2 + 1], lazy[ind]);
        }
        lazy[ind] = 0;
    }
    void update(int ind, int l, int r, int x, int y, int val) {
        if(lazy[ind]) down(ind, l, r);
        if(l > y || r < x) return;
        if(x <= l and r <= y) {
            lazy[ind] = val;
            down(ind, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(ind * 2, l, mid, x, y, val);
        update(ind * 2 + 1, mid + 1, r, x, y, val);
        tree[ind] = min(tree[ind * 2], tree[ind * 2 + 1]);
    }
    int get(int ind, int l, int r, int x, int y) {
        if(lazy[ind]) down(ind, l, r);
        if(l > y || r < x) return n + 1;
        if(x <= l and r <= y) return tree[ind];
        int mid = (l + r) / 2;
        return min(get(ind * 2, l, mid, x, y), get(ind * 2 + 1, mid + 1, r, x, y));
    }
    void update(int x, int y, int val) {
        update(1, 1, n, x, y, val);
    }
    int get(int x, int y) {
        return get(1, 1, n, x, y);
    }
} st; 
void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i) {
        int l, r; cin >> l >> r;
        segment[r].push_back(l);
    }
    st = segment_tree(n);
    for(int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        que[r].push_back({l, i});
    }
    for(int i = 1; i <= n; ++i) {
        for(auto l:segment[i]) {
            st.update(l, i, l);
        }
        for(auto e:que[i]) {
            ans[e.second] = (st.get(e.first, i) >= e.first);
        }
    }
    for(int i = 1; i <= q; ++i) {
        cout << (ans[i] ? "YES\n" : "NO\n");
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 6 ms 24924 KB Output is correct
3 Correct 7 ms 25028 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 6 ms 25104 KB Output is correct
6 Correct 6 ms 24924 KB Output is correct
7 Correct 6 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 6 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 24928 KB Output is correct
12 Correct 5 ms 24980 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 6 ms 24924 KB Output is correct
3 Correct 7 ms 25028 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 6 ms 25104 KB Output is correct
6 Correct 6 ms 24924 KB Output is correct
7 Correct 6 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 6 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 24928 KB Output is correct
12 Correct 5 ms 24980 KB Output is correct
13 Correct 8 ms 25180 KB Output is correct
14 Correct 7 ms 25152 KB Output is correct
15 Correct 7 ms 25020 KB Output is correct
16 Correct 8 ms 25120 KB Output is correct
17 Correct 6 ms 25240 KB Output is correct
18 Correct 6 ms 25040 KB Output is correct
19 Correct 5 ms 25176 KB Output is correct
20 Correct 7 ms 25176 KB Output is correct
21 Correct 6 ms 25180 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 6 ms 24924 KB Output is correct
3 Correct 7 ms 25028 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 6 ms 25104 KB Output is correct
6 Correct 6 ms 24924 KB Output is correct
7 Correct 6 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 6 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 24928 KB Output is correct
12 Correct 5 ms 24980 KB Output is correct
13 Correct 8 ms 25180 KB Output is correct
14 Correct 7 ms 25152 KB Output is correct
15 Correct 7 ms 25020 KB Output is correct
16 Correct 8 ms 25120 KB Output is correct
17 Correct 6 ms 25240 KB Output is correct
18 Correct 6 ms 25040 KB Output is correct
19 Correct 5 ms 25176 KB Output is correct
20 Correct 7 ms 25176 KB Output is correct
21 Correct 6 ms 25180 KB Output is correct
22 Correct 126 ms 37332 KB Output is correct
23 Correct 145 ms 37796 KB Output is correct
24 Correct 156 ms 39252 KB Output is correct
25 Correct 272 ms 44884 KB Output is correct
26 Correct 124 ms 37460 KB Output is correct
27 Correct 266 ms 44880 KB Output is correct
28 Correct 277 ms 44904 KB Output is correct
29 Correct 127 ms 36504 KB Output is correct
30 Correct 80 ms 36692 KB Output is correct
31 Correct 101 ms 37372 KB Output is correct
32 Correct 220 ms 44112 KB Output is correct
33 Correct 77 ms 36656 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 6 ms 25092 KB Output is correct
5 Correct 7 ms 25180 KB Output is correct
6 Correct 6 ms 25176 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 80 ms 36728 KB Output is correct
9 Correct 92 ms 37460 KB Output is correct
10 Correct 222 ms 44124 KB Output is correct
11 Correct 84 ms 36688 KB Output is correct
12 Correct 82 ms 33504 KB Output is correct
13 Correct 83 ms 33364 KB Output is correct
14 Correct 60 ms 33620 KB Output is correct
15 Correct 66 ms 33092 KB Output is correct
16 Correct 62 ms 33444 KB Output is correct
17 Correct 61 ms 33104 KB Output is correct
18 Correct 595 ms 69720 KB Output is correct
19 Correct 564 ms 69972 KB Output is correct
20 Correct 420 ms 70484 KB Output is correct
21 Correct 389 ms 69592 KB Output is correct
22 Correct 401 ms 68948 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 6 ms 24924 KB Output is correct
3 Correct 7 ms 25028 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 6 ms 25104 KB Output is correct
6 Correct 6 ms 24924 KB Output is correct
7 Correct 6 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 6 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 24928 KB Output is correct
12 Correct 5 ms 24980 KB Output is correct
13 Correct 8 ms 25180 KB Output is correct
14 Correct 7 ms 25152 KB Output is correct
15 Correct 7 ms 25020 KB Output is correct
16 Correct 8 ms 25120 KB Output is correct
17 Correct 6 ms 25240 KB Output is correct
18 Correct 6 ms 25040 KB Output is correct
19 Correct 5 ms 25176 KB Output is correct
20 Correct 7 ms 25176 KB Output is correct
21 Correct 6 ms 25180 KB Output is correct
22 Correct 88 ms 29592 KB Output is correct
23 Correct 87 ms 29716 KB Output is correct
24 Correct 102 ms 32696 KB Output is correct
25 Correct 102 ms 32620 KB Output is correct
26 Correct 74 ms 34132 KB Output is correct
27 Correct 79 ms 34128 KB Output is correct
28 Correct 63 ms 31828 KB Output is correct
29 Correct 73 ms 33364 KB Output is correct
30 Correct 103 ms 32592 KB Output is correct
31 Correct 102 ms 32604 KB Output is correct
32 Correct 91 ms 33108 KB Output is correct
33 Correct 86 ms 33364 KB Output is correct
34 Correct 101 ms 32164 KB Output is correct
35 Correct 89 ms 32548 KB Output is correct
36 Correct 86 ms 33108 KB Output is correct
37 Correct 83 ms 33424 KB Output is correct
38 Correct 80 ms 33364 KB Output is correct
39 Correct 61 ms 33496 KB Output is correct
40 Correct 64 ms 33236 KB Output is correct
41 Correct 68 ms 33584 KB Output is correct
42 Correct 65 ms 33108 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 6 ms 24924 KB Output is correct
3 Correct 7 ms 25028 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 6 ms 25104 KB Output is correct
6 Correct 6 ms 24924 KB Output is correct
7 Correct 6 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 6 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 24928 KB Output is correct
12 Correct 5 ms 24980 KB Output is correct
13 Correct 8 ms 25180 KB Output is correct
14 Correct 7 ms 25152 KB Output is correct
15 Correct 7 ms 25020 KB Output is correct
16 Correct 8 ms 25120 KB Output is correct
17 Correct 6 ms 25240 KB Output is correct
18 Correct 6 ms 25040 KB Output is correct
19 Correct 5 ms 25176 KB Output is correct
20 Correct 7 ms 25176 KB Output is correct
21 Correct 6 ms 25180 KB Output is correct
22 Correct 126 ms 37332 KB Output is correct
23 Correct 145 ms 37796 KB Output is correct
24 Correct 156 ms 39252 KB Output is correct
25 Correct 272 ms 44884 KB Output is correct
26 Correct 124 ms 37460 KB Output is correct
27 Correct 266 ms 44880 KB Output is correct
28 Correct 277 ms 44904 KB Output is correct
29 Correct 127 ms 36504 KB Output is correct
30 Correct 80 ms 36692 KB Output is correct
31 Correct 101 ms 37372 KB Output is correct
32 Correct 220 ms 44112 KB Output is correct
33 Correct 77 ms 36656 KB Output is correct
34 Correct 5 ms 24920 KB Output is correct
35 Correct 5 ms 24924 KB Output is correct
36 Correct 5 ms 24924 KB Output is correct
37 Correct 6 ms 25092 KB Output is correct
38 Correct 7 ms 25180 KB Output is correct
39 Correct 6 ms 25176 KB Output is correct
40 Correct 6 ms 25180 KB Output is correct
41 Correct 80 ms 36728 KB Output is correct
42 Correct 92 ms 37460 KB Output is correct
43 Correct 222 ms 44124 KB Output is correct
44 Correct 84 ms 36688 KB Output is correct
45 Correct 82 ms 33504 KB Output is correct
46 Correct 83 ms 33364 KB Output is correct
47 Correct 60 ms 33620 KB Output is correct
48 Correct 66 ms 33092 KB Output is correct
49 Correct 62 ms 33444 KB Output is correct
50 Correct 61 ms 33104 KB Output is correct
51 Correct 595 ms 69720 KB Output is correct
52 Correct 564 ms 69972 KB Output is correct
53 Correct 420 ms 70484 KB Output is correct
54 Correct 389 ms 69592 KB Output is correct
55 Correct 401 ms 68948 KB Output is correct
56 Correct 88 ms 29592 KB Output is correct
57 Correct 87 ms 29716 KB Output is correct
58 Correct 102 ms 32696 KB Output is correct
59 Correct 102 ms 32620 KB Output is correct
60 Correct 74 ms 34132 KB Output is correct
61 Correct 79 ms 34128 KB Output is correct
62 Correct 63 ms 31828 KB Output is correct
63 Correct 73 ms 33364 KB Output is correct
64 Correct 103 ms 32592 KB Output is correct
65 Correct 102 ms 32604 KB Output is correct
66 Correct 91 ms 33108 KB Output is correct
67 Correct 86 ms 33364 KB Output is correct
68 Correct 101 ms 32164 KB Output is correct
69 Correct 89 ms 32548 KB Output is correct
70 Correct 86 ms 33108 KB Output is correct
71 Correct 83 ms 33424 KB Output is correct
72 Correct 80 ms 33364 KB Output is correct
73 Correct 61 ms 33496 KB Output is correct
74 Correct 64 ms 33236 KB Output is correct
75 Correct 68 ms 33584 KB Output is correct
76 Correct 65 ms 33108 KB Output is correct
77 Correct 600 ms 66388 KB Output is correct
78 Correct 622 ms 66208 KB Output is correct
79 Correct 448 ms 72788 KB Output is correct
80 Correct 474 ms 73040 KB Output is correct
81 Correct 453 ms 70736 KB Output is correct
82 Correct 465 ms 71760 KB Output is correct
83 Correct 701 ms 66620 KB Output is correct
84 Correct 689 ms 66208 KB Output is correct
85 Correct 703 ms 67816 KB Output is correct
86 Correct 625 ms 64528 KB Output is correct
87 Correct 675 ms 64144 KB Output is correct
88 Correct 609 ms 70828 KB Output is correct