oj.uz

Submission #930889

# Submission time Handle Problem Language Result Execution time Memory
930889 2024-02-20T15:13:15 Z vjudge1 Curtains (NOI23_curtains) C++17
100 / 100
 831 ms 80328 KB 
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int t[2000005], tt[2000005], res[500005];
vector<int> g[500005];
vector<pair<int, int>> gg[500005];
void update(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && r == tr) {
        t[v] = min(t[v], x);
        tt[v] = min(tt[v], x);
        return;
    }
    int mid = (tl + tr) / 2;
    update(v * 2, tl, mid, l, min(r, mid), x);
    update(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
    t[v] = min(max(t[v * 2], t[v * 2 + 1]), tt[v]);
}
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 1e9 + 1;
    if (tl == l && tr == r) {
        return t[v];
    }
    int mid = (tl + tr) / 2;
    int h = sum(v * 2, tl, mid, l, min(r, mid)), k = sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
    if (h == 1e9 + 1) return min(k, tt[v]);
    if (k == 1e9 + 1) return min(h, tt[v]);
    return min(max(h, k), tt[v]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        gg[u].push_back({v, i});
    }
    for (int i = 1; i <= n * 4; i++) t[i] = tt[i] = 1e9;
    for (int i = n; i >= 1; i--) {
        for (int w : g[i]) {
            update(1, 1, n, i, w, w);
        }
        for (auto w : gg[i]) {
            if (sum(1, 1, n, i, w.first) <= w.first) {
                res[w.second] = 1;
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (res[i] == 0) cout << "NO";
        else cout << "YES";
        cout << '\n';
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29276 KB Output is correct
2 Correct 7 ms 29320 KB Output is correct
3 Correct 7 ms 29356 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 9 ms 29276 KB Output is correct
6 Correct 7 ms 29364 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29384 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29364 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 8 ms 29364 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29276 KB Output is correct
2 Correct 7 ms 29320 KB Output is correct
3 Correct 7 ms 29356 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 9 ms 29276 KB Output is correct
6 Correct 7 ms 29364 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29384 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29364 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 8 ms 29364 KB Output is correct
13 Correct 9 ms 29276 KB Output is correct
14 Correct 9 ms 29276 KB Output is correct
15 Correct 9 ms 29276 KB Output is correct
16 Correct 9 ms 29384 KB Output is correct
17 Correct 12 ms 29276 KB Output is correct
18 Correct 9 ms 29276 KB Output is correct
19 Correct 9 ms 29276 KB Output is correct
20 Correct 10 ms 29324 KB Output is correct
21 Correct 9 ms 29276 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29276 KB Output is correct
2 Correct 7 ms 29320 KB Output is correct
3 Correct 7 ms 29356 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 9 ms 29276 KB Output is correct
6 Correct 7 ms 29364 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29384 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29364 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 8 ms 29364 KB Output is correct
13 Correct 9 ms 29276 KB Output is correct
14 Correct 9 ms 29276 KB Output is correct
15 Correct 9 ms 29276 KB Output is correct
16 Correct 9 ms 29384 KB Output is correct
17 Correct 12 ms 29276 KB Output is correct
18 Correct 9 ms 29276 KB Output is correct
19 Correct 9 ms 29276 KB Output is correct
20 Correct 10 ms 29324 KB Output is correct
21 Correct 9 ms 29276 KB Output is correct
22 Correct 179 ms 39252 KB Output is correct
23 Correct 180 ms 39916 KB Output is correct
24 Correct 203 ms 41040 KB Output is correct
25 Correct 311 ms 44812 KB Output is correct
26 Correct 181 ms 39824 KB Output is correct
27 Correct 312 ms 44832 KB Output is correct
28 Correct 316 ms 44880 KB Output is correct
29 Correct 172 ms 39508 KB Output is correct
30 Correct 137 ms 37044 KB Output is correct
31 Correct 143 ms 37636 KB Output is correct
32 Correct 267 ms 42532 KB Output is correct
33 Correct 129 ms 37164 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29276 KB Output is correct
2 Correct 7 ms 29356 KB Output is correct
3 Correct 8 ms 29276 KB Output is correct
4 Correct 7 ms 29272 KB Output is correct
5 Correct 10 ms 29468 KB Output is correct
6 Correct 9 ms 29276 KB Output is correct
7 Correct 9 ms 29272 KB Output is correct
8 Correct 132 ms 36908 KB Output is correct
9 Correct 143 ms 37616 KB Output is correct
10 Correct 283 ms 42680 KB Output is correct
11 Correct 130 ms 37084 KB Output is correct
12 Correct 93 ms 35528 KB Output is correct
13 Correct 103 ms 35704 KB Output is correct
14 Correct 76 ms 35832 KB Output is correct
15 Correct 97 ms 35816 KB Output is correct
16 Correct 77 ms 35836 KB Output is correct
17 Correct 79 ms 35828 KB Output is correct
18 Correct 526 ms 61648 KB Output is correct
19 Correct 559 ms 61720 KB Output is correct
20 Correct 460 ms 62420 KB Output is correct
21 Correct 433 ms 62360 KB Output is correct
22 Correct 469 ms 62472 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29276 KB Output is correct
2 Correct 7 ms 29320 KB Output is correct
3 Correct 7 ms 29356 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 9 ms 29276 KB Output is correct
6 Correct 7 ms 29364 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29384 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29364 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 8 ms 29364 KB Output is correct
13 Correct 9 ms 29276 KB Output is correct
14 Correct 9 ms 29276 KB Output is correct
15 Correct 9 ms 29276 KB Output is correct
16 Correct 9 ms 29384 KB Output is correct
17 Correct 12 ms 29276 KB Output is correct
18 Correct 9 ms 29276 KB Output is correct
19 Correct 9 ms 29276 KB Output is correct
20 Correct 10 ms 29324 KB Output is correct
21 Correct 9 ms 29276 KB Output is correct
22 Correct 91 ms 33104 KB Output is correct
23 Correct 93 ms 33060 KB Output is correct
24 Correct 120 ms 36604 KB Output is correct
25 Correct 131 ms 36688 KB Output is correct
26 Correct 109 ms 38436 KB Output is correct
27 Correct 102 ms 38480 KB Output is correct
28 Correct 107 ms 36284 KB Output is correct
29 Correct 99 ms 37728 KB Output is correct
30 Correct 120 ms 36692 KB Output is correct
31 Correct 130 ms 36720 KB Output is correct
32 Correct 121 ms 36940 KB Output is correct
33 Correct 102 ms 37204 KB Output is correct
34 Correct 111 ms 36748 KB Output is correct
35 Correct 116 ms 36328 KB Output is correct
36 Correct 108 ms 36732 KB Output is correct
37 Correct 93 ms 35512 KB Output is correct
38 Correct 95 ms 35564 KB Output is correct
39 Correct 101 ms 35964 KB Output is correct
40 Correct 86 ms 35816 KB Output is correct
41 Correct 112 ms 36052 KB Output is correct
42 Correct 82 ms 36324 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29276 KB Output is correct
2 Correct 7 ms 29320 KB Output is correct
3 Correct 7 ms 29356 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 9 ms 29276 KB Output is correct
6 Correct 7 ms 29364 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29384 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29364 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 8 ms 29364 KB Output is correct
13 Correct 9 ms 29276 KB Output is correct
14 Correct 9 ms 29276 KB Output is correct
15 Correct 9 ms 29276 KB Output is correct
16 Correct 9 ms 29384 KB Output is correct
17 Correct 12 ms 29276 KB Output is correct
18 Correct 9 ms 29276 KB Output is correct
19 Correct 9 ms 29276 KB Output is correct
20 Correct 10 ms 29324 KB Output is correct
21 Correct 9 ms 29276 KB Output is correct
22 Correct 179 ms 39252 KB Output is correct
23 Correct 180 ms 39916 KB Output is correct
24 Correct 203 ms 41040 KB Output is correct
25 Correct 311 ms 44812 KB Output is correct
26 Correct 181 ms 39824 KB Output is correct
27 Correct 312 ms 44832 KB Output is correct
28 Correct 316 ms 44880 KB Output is correct
29 Correct 172 ms 39508 KB Output is correct
30 Correct 137 ms 37044 KB Output is correct
31 Correct 143 ms 37636 KB Output is correct
32 Correct 267 ms 42532 KB Output is correct
33 Correct 129 ms 37164 KB Output is correct
34 Correct 7 ms 29276 KB Output is correct
35 Correct 7 ms 29356 KB Output is correct
36 Correct 8 ms 29276 KB Output is correct
37 Correct 7 ms 29272 KB Output is correct
38 Correct 10 ms 29468 KB Output is correct
39 Correct 9 ms 29276 KB Output is correct
40 Correct 9 ms 29272 KB Output is correct
41 Correct 132 ms 36908 KB Output is correct
42 Correct 143 ms 37616 KB Output is correct
43 Correct 283 ms 42680 KB Output is correct
44 Correct 130 ms 37084 KB Output is correct
45 Correct 93 ms 35528 KB Output is correct
46 Correct 103 ms 35704 KB Output is correct
47 Correct 76 ms 35832 KB Output is correct
48 Correct 97 ms 35816 KB Output is correct
49 Correct 77 ms 35836 KB Output is correct
50 Correct 79 ms 35828 KB Output is correct
51 Correct 526 ms 61648 KB Output is correct
52 Correct 559 ms 61720 KB Output is correct
53 Correct 460 ms 62420 KB Output is correct
54 Correct 433 ms 62360 KB Output is correct
55 Correct 469 ms 62472 KB Output is correct
56 Correct 91 ms 33104 KB Output is correct
57 Correct 93 ms 33060 KB Output is correct
58 Correct 120 ms 36604 KB Output is correct
59 Correct 131 ms 36688 KB Output is correct
60 Correct 109 ms 38436 KB Output is correct
61 Correct 102 ms 38480 KB Output is correct
62 Correct 107 ms 36284 KB Output is correct
63 Correct 99 ms 37728 KB Output is correct
64 Correct 120 ms 36692 KB Output is correct
65 Correct 130 ms 36720 KB Output is correct
66 Correct 121 ms 36940 KB Output is correct
67 Correct 102 ms 37204 KB Output is correct
68 Correct 111 ms 36748 KB Output is correct
69 Correct 116 ms 36328 KB Output is correct
70 Correct 108 ms 36732 KB Output is correct
71 Correct 93 ms 35512 KB Output is correct
72 Correct 95 ms 35564 KB Output is correct
73 Correct 101 ms 35964 KB Output is correct
74 Correct 86 ms 35816 KB Output is correct
75 Correct 112 ms 36052 KB Output is correct
76 Correct 82 ms 36324 KB Output is correct
77 Correct 831 ms 72192 KB Output is correct
78 Correct 827 ms 72248 KB Output is correct
79 Correct 692 ms 80144 KB Output is correct
80 Correct 682 ms 80328 KB Output is correct
81 Correct 699 ms 77844 KB Output is correct
82 Correct 684 ms 75652 KB Output is correct
83 Correct 785 ms 68748 KB Output is correct
84 Correct 786 ms 69136 KB Output is correct
85 Correct 737 ms 69852 KB Output is correct
86 Correct 675 ms 65604 KB Output is correct
87 Correct 653 ms 65464 KB Output is correct
88 Correct 677 ms 73044 KB Output is correct