oj.uz

Submission #1116417

# Submission time Handle Problem Language Result Execution time Memory
1116417 2024-11-21T15:46:41 Z hngwlog Curtains (NOI23_curtains) C++17
100 / 100
 775 ms 173220 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & -i)
#define FORB0(n, i, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

struct queryNode {

    int v, id;

    bool operator < (const queryNode o) const {

        return v < o.v;
    }
};

int n, m, q;
vector<bool> ans;
vector<vector<int>> adjL, adjR, p, pRv;
vector<vector<queryNode>> query;

void DAC(int cnt, int l, int r) {

    if (l == r) {
        while (_size(query[l])) {
            if (_size(adjL[l]) && adjL[l][0] == l) ans[query[l].back().id] = 1;
            else ans[query[l].back().id] = 0;
            query[l].pop_back();
        }
        return ;
    }
    int mid = (l + r) / 2;
    int pos = lower_bound(adjL[mid].begin(), adjL[mid].end(), mid) - adjL[mid].begin();
    p[cnt][mid] = (pos == _size(adjL[mid]) ? - 1 : adjL[mid][pos]);
    stack<int> st;
    if (p[cnt][mid] != - 1) st.push(mid);
    FORD(i, mid - 1, l) {
        pos = lower_bound(adjL[i].begin(), adjL[i].end(), mid) - adjL[i].begin();
        int best = - 1;
        if (pos != _size(adjL[i])) best = adjL[i][pos];
        if (pos) {
            pos--;
            while (!st.empty() && st.top() <= adjL[i][pos] + 1) {
                if (best == - 1 || best > p[cnt][st.top()]) best = p[cnt][st.top()];
                st.pop();
            }
        }
        p[cnt][i] = best;
        if (best != - 1) st.push(i);
    }
    while (!st.empty()) st.pop();
    pos = upper_bound(adjR[mid + 1].begin(), adjR[mid + 1].end(), mid + 1) - adjR[mid + 1].begin();
    pRv[cnt][mid + 1] = (!pos ? - 1 : adjR[mid + 1][pos - 1]);
    if (pRv[cnt][mid + 1] != - 1) st.push(mid + 1);
    FOR(i, mid + 2, r) {
        pos = upper_bound(adjR[i].begin(), adjR[i].end(), mid + 1) - adjR[i].begin();
        int best = - 1;
        if (pos) best = adjR[i][pos - 1];
        if (pos != _size(adjR[i])) {
            while (!st.empty() && st.top() >= adjR[i][pos] - 1) {
                if (best == - 1 || best < pRv[cnt][st.top()]) best = pRv[cnt][st.top()];
                st.pop();
            }
        }
        pRv[cnt][i] = best;
        if (best != - 1) st.push(i);
    }
    FOR(u, l, mid) {
        int v;
        while (_size(query[u]) && (v = query[u].back().v) > mid) {
            if (p[cnt][u] == - 1 || pRv[cnt][v] == - 1 || p[cnt][u] > v || pRv[cnt][v] < u) ans[query[u].back().id] = 0;
            else ans[query[u].back().id] = 1;
            query[u].pop_back();
        }
    }
    DAC(cnt + 1, l, mid);
    DAC(cnt + 1, mid + 1, r);
}

int main() {
    fastio;

    cin >> n >> m >> q;
    adjL.resize(n + 1);
    adjR.resize(n + 1);
    REP(i, m) {
        int l, r;
        cin >> l >> r;
        adjL[l].push_back(r);
        adjR[r].push_back(l);
    }
    FOR(i, 1, n) {
        sort(adjL[i].begin(), adjL[i].end());
        sort(adjR[i].begin(), adjR[i].end());
    }
    query.resize(n + 1);
    REP(i, q) {
        int u, v;
        cin >> u >> v;
        query[u].push_back({v, i});
    }
    FOR(i, 1, n) sort(query[i].begin(), query[i].end());
    ans.resize(q);
    p.assign(20, vector<int>(n + 1));
    pRv.assign(20, vector<int>(n + 1));
    DAC(0, 1, n);
    REP(i, q) {
        if (ans[i]) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 504 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 504 KB Output is correct
13 Correct 3 ms 884 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 2 ms 916 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 2 ms 988 KB Output is correct
18 Correct 3 ms 916 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 1104 KB Output is correct
21 Correct 2 ms 964 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 504 KB Output is correct
13 Correct 3 ms 884 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 2 ms 916 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 2 ms 988 KB Output is correct
18 Correct 3 ms 916 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 1104 KB Output is correct
21 Correct 2 ms 964 KB Output is correct
22 Correct 81 ms 12872 KB Output is correct
23 Correct 88 ms 13548 KB Output is correct
24 Correct 102 ms 15688 KB Output is correct
25 Correct 186 ms 23624 KB Output is correct
26 Correct 89 ms 13384 KB Output is correct
27 Correct 177 ms 23624 KB Output is correct
28 Correct 181 ms 23632 KB Output is correct
29 Correct 88 ms 13128 KB Output is correct
30 Correct 81 ms 10160 KB Output is correct
31 Correct 92 ms 11184 KB Output is correct
32 Correct 174 ms 20912 KB Output is correct
33 Correct 95 ms 10524 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 3 ms 1104 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 80 ms 10288 KB Output is correct
9 Correct 92 ms 11188 KB Output is correct
10 Correct 187 ms 20912 KB Output is correct
11 Correct 81 ms 10416 KB Output is correct
12 Correct 85 ms 30144 KB Output is correct
13 Correct 83 ms 30048 KB Output is correct
14 Correct 87 ms 30400 KB Output is correct
15 Correct 80 ms 30048 KB Output is correct
16 Correct 81 ms 30408 KB Output is correct
17 Correct 81 ms 29884 KB Output is correct
18 Correct 606 ms 150196 KB Output is correct
19 Correct 565 ms 150444 KB Output is correct
20 Correct 588 ms 151980 KB Output is correct
21 Correct 577 ms 151220 KB Output is correct
22 Correct 521 ms 150188 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 504 KB Output is correct
13 Correct 3 ms 884 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 2 ms 916 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 2 ms 988 KB Output is correct
18 Correct 3 ms 916 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 1104 KB Output is correct
21 Correct 2 ms 964 KB Output is correct
22 Correct 41 ms 7752 KB Output is correct
23 Correct 41 ms 7752 KB Output is correct
24 Correct 84 ms 31740 KB Output is correct
25 Correct 85 ms 31680 KB Output is correct
26 Correct 86 ms 34496 KB Output is correct
27 Correct 81 ms 34548 KB Output is correct
28 Correct 72 ms 30656 KB Output is correct
29 Correct 78 ms 33684 KB Output is correct
30 Correct 87 ms 31680 KB Output is correct
31 Correct 108 ms 31612 KB Output is correct
32 Correct 103 ms 32280 KB Output is correct
33 Correct 103 ms 32960 KB Output is correct
34 Correct 91 ms 31424 KB Output is correct
35 Correct 86 ms 31168 KB Output is correct
36 Correct 84 ms 31980 KB Output is correct
37 Correct 82 ms 30144 KB Output is correct
38 Correct 87 ms 30028 KB Output is correct
39 Correct 85 ms 30400 KB Output is correct
40 Correct 90 ms 29884 KB Output is correct
41 Correct 86 ms 30444 KB Output is correct
42 Correct 84 ms 30020 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 504 KB Output is correct
13 Correct 3 ms 884 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 2 ms 916 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 2 ms 988 KB Output is correct
18 Correct 3 ms 916 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 1104 KB Output is correct
21 Correct 2 ms 964 KB Output is correct
22 Correct 81 ms 12872 KB Output is correct
23 Correct 88 ms 13548 KB Output is correct
24 Correct 102 ms 15688 KB Output is correct
25 Correct 186 ms 23624 KB Output is correct
26 Correct 89 ms 13384 KB Output is correct
27 Correct 177 ms 23624 KB Output is correct
28 Correct 181 ms 23632 KB Output is correct
29 Correct 88 ms 13128 KB Output is correct
30 Correct 81 ms 10160 KB Output is correct
31 Correct 92 ms 11184 KB Output is correct
32 Correct 174 ms 20912 KB Output is correct
33 Correct 95 ms 10524 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 504 KB Output is correct
37 Correct 1 ms 508 KB Output is correct
38 Correct 2 ms 848 KB Output is correct
39 Correct 3 ms 1104 KB Output is correct
40 Correct 2 ms 848 KB Output is correct
41 Correct 80 ms 10288 KB Output is correct
42 Correct 92 ms 11188 KB Output is correct
43 Correct 187 ms 20912 KB Output is correct
44 Correct 81 ms 10416 KB Output is correct
45 Correct 85 ms 30144 KB Output is correct
46 Correct 83 ms 30048 KB Output is correct
47 Correct 87 ms 30400 KB Output is correct
48 Correct 80 ms 30048 KB Output is correct
49 Correct 81 ms 30408 KB Output is correct
50 Correct 81 ms 29884 KB Output is correct
51 Correct 606 ms 150196 KB Output is correct
52 Correct 565 ms 150444 KB Output is correct
53 Correct 588 ms 151980 KB Output is correct
54 Correct 577 ms 151220 KB Output is correct
55 Correct 521 ms 150188 KB Output is correct
56 Correct 41 ms 7752 KB Output is correct
57 Correct 41 ms 7752 KB Output is correct
58 Correct 84 ms 31740 KB Output is correct
59 Correct 85 ms 31680 KB Output is correct
60 Correct 86 ms 34496 KB Output is correct
61 Correct 81 ms 34548 KB Output is correct
62 Correct 72 ms 30656 KB Output is correct
63 Correct 78 ms 33684 KB Output is correct
64 Correct 87 ms 31680 KB Output is correct
65 Correct 108 ms 31612 KB Output is correct
66 Correct 103 ms 32280 KB Output is correct
67 Correct 103 ms 32960 KB Output is correct
68 Correct 91 ms 31424 KB Output is correct
69 Correct 86 ms 31168 KB Output is correct
70 Correct 84 ms 31980 KB Output is correct
71 Correct 82 ms 30144 KB Output is correct
72 Correct 87 ms 30028 KB Output is correct
73 Correct 85 ms 30400 KB Output is correct
74 Correct 90 ms 29884 KB Output is correct
75 Correct 86 ms 30444 KB Output is correct
76 Correct 84 ms 30020 KB Output is correct
77 Correct 721 ms 158736 KB Output is correct
78 Correct 705 ms 158628 KB Output is correct
79 Correct 775 ms 173056 KB Output is correct
80 Correct 744 ms 173220 KB Output is correct
81 Correct 715 ms 169212 KB Output is correct
82 Correct 695 ms 171940 KB Output is correct
83 Correct 735 ms 158560 KB Output is correct
84 Correct 692 ms 158884 KB Output is correct
85 Correct 756 ms 160664 KB Output is correct
86 Correct 566 ms 154780 KB Output is correct
87 Correct 516 ms 154228 KB Output is correct
88 Correct 660 ms 168300 KB Output is correct