oj.uz

Submission #1117229

# Submission time Handle Problem Language Result Execution time Memory
1117229 2024-11-23T04:23:40 Z DP_196 Curtains (NOI23_curtains) C++14
100 / 100
 931 ms 153840 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;
}
 
/*
https://oj.uz/problem/view/NOI23_curtains
both segtree are nice :D
*/

Compilation message

curtains.cpp: In function 'int main()':
curtains.cpp:179:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  179 |         for (auto [l, id] : query[r]) {
      |                   ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48976 KB Output is correct
2 Correct 21 ms 48976 KB Output is correct
3 Correct 22 ms 48976 KB Output is correct
4 Correct 21 ms 47440 KB Output is correct
5 Correct 26 ms 47440 KB Output is correct
6 Correct 26 ms 47332 KB Output is correct
7 Correct 26 ms 47432 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 27 ms 47308 KB Output is correct
10 Correct 25 ms 47260 KB Output is correct
11 Correct 25 ms 47440 KB Output is correct
12 Correct 26 ms 47340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48976 KB Output is correct
2 Correct 21 ms 48976 KB Output is correct
3 Correct 22 ms 48976 KB Output is correct
4 Correct 21 ms 47440 KB Output is correct
5 Correct 26 ms 47440 KB Output is correct
6 Correct 26 ms 47332 KB Output is correct
7 Correct 26 ms 47432 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 27 ms 47308 KB Output is correct
10 Correct 25 ms 47260 KB Output is correct
11 Correct 25 ms 47440 KB Output is correct
12 Correct 26 ms 47340 KB Output is correct
13 Correct 24 ms 47696 KB Output is correct
14 Correct 28 ms 47572 KB Output is correct
15 Correct 28 ms 47696 KB Output is correct
16 Correct 24 ms 47688 KB Output is correct
17 Correct 23 ms 49512 KB Output is correct
18 Correct 23 ms 47696 KB Output is correct
19 Correct 25 ms 47824 KB Output is correct
20 Correct 26 ms 47696 KB Output is correct
21 Correct 29 ms 47696 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48976 KB Output is correct
2 Correct 21 ms 48976 KB Output is correct
3 Correct 22 ms 48976 KB Output is correct
4 Correct 21 ms 47440 KB Output is correct
5 Correct 26 ms 47440 KB Output is correct
6 Correct 26 ms 47332 KB Output is correct
7 Correct 26 ms 47432 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 27 ms 47308 KB Output is correct
10 Correct 25 ms 47260 KB Output is correct
11 Correct 25 ms 47440 KB Output is correct
12 Correct 26 ms 47340 KB Output is correct
13 Correct 24 ms 47696 KB Output is correct
14 Correct 28 ms 47572 KB Output is correct
15 Correct 28 ms 47696 KB Output is correct
16 Correct 24 ms 47688 KB Output is correct
17 Correct 23 ms 49512 KB Output is correct
18 Correct 23 ms 47696 KB Output is correct
19 Correct 25 ms 47824 KB Output is correct
20 Correct 26 ms 47696 KB Output is correct
21 Correct 29 ms 47696 KB Output is correct
22 Correct 157 ms 61512 KB Output is correct
23 Correct 164 ms 62044 KB Output is correct
24 Correct 236 ms 63228 KB Output is correct
25 Correct 342 ms 69200 KB Output is correct
26 Correct 167 ms 61768 KB Output is correct
27 Correct 324 ms 69192 KB Output is correct
28 Correct 330 ms 69248 KB Output is correct
29 Correct 152 ms 60744 KB Output is correct
30 Correct 117 ms 60744 KB Output is correct
31 Correct 137 ms 61756 KB Output is correct
32 Correct 283 ms 69960 KB Output is correct
33 Correct 155 ms 62536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48976 KB Output is correct
2 Correct 16 ms 48976 KB Output is correct
3 Correct 24 ms 48976 KB Output is correct
4 Correct 22 ms 48976 KB Output is correct
5 Correct 23 ms 47696 KB Output is correct
6 Correct 23 ms 47696 KB Output is correct
7 Correct 21 ms 49488 KB Output is correct
8 Correct 112 ms 62416 KB Output is correct
9 Correct 136 ms 63316 KB Output is correct
10 Correct 283 ms 69972 KB Output is correct
11 Correct 118 ms 60832 KB Output is correct
12 Correct 130 ms 69192 KB Output is correct
13 Correct 130 ms 67400 KB Output is correct
14 Correct 112 ms 67656 KB Output is correct
15 Correct 116 ms 67016 KB Output is correct
16 Correct 120 ms 67400 KB Output is correct
17 Correct 132 ms 67144 KB Output is correct
18 Correct 758 ms 149320 KB Output is correct
19 Correct 773 ms 150856 KB Output is correct
20 Correct 639 ms 149828 KB Output is correct
21 Correct 621 ms 149064 KB Output is correct
22 Correct 652 ms 148548 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48976 KB Output is correct
2 Correct 21 ms 48976 KB Output is correct
3 Correct 22 ms 48976 KB Output is correct
4 Correct 21 ms 47440 KB Output is correct
5 Correct 26 ms 47440 KB Output is correct
6 Correct 26 ms 47332 KB Output is correct
7 Correct 26 ms 47432 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 27 ms 47308 KB Output is correct
10 Correct 25 ms 47260 KB Output is correct
11 Correct 25 ms 47440 KB Output is correct
12 Correct 26 ms 47340 KB Output is correct
13 Correct 24 ms 47696 KB Output is correct
14 Correct 28 ms 47572 KB Output is correct
15 Correct 28 ms 47696 KB Output is correct
16 Correct 24 ms 47688 KB Output is correct
17 Correct 23 ms 49512 KB Output is correct
18 Correct 23 ms 47696 KB Output is correct
19 Correct 25 ms 47824 KB Output is correct
20 Correct 26 ms 47696 KB Output is correct
21 Correct 29 ms 47696 KB Output is correct
22 Correct 113 ms 53320 KB Output is correct
23 Correct 108 ms 55112 KB Output is correct
24 Correct 154 ms 68424 KB Output is correct
25 Correct 167 ms 68424 KB Output is correct
26 Correct 132 ms 67912 KB Output is correct
27 Correct 150 ms 67912 KB Output is correct
28 Correct 113 ms 65864 KB Output is correct
29 Correct 129 ms 69300 KB Output is correct
30 Correct 143 ms 68472 KB Output is correct
31 Correct 152 ms 66588 KB Output is correct
32 Correct 159 ms 67032 KB Output is correct
33 Correct 146 ms 67400 KB Output is correct
34 Correct 157 ms 66120 KB Output is correct
35 Correct 148 ms 68232 KB Output is correct
36 Correct 150 ms 68732 KB Output is correct
37 Correct 151 ms 69028 KB Output is correct
38 Correct 142 ms 69192 KB Output is correct
39 Correct 143 ms 67668 KB Output is correct
40 Correct 113 ms 67144 KB Output is correct
41 Correct 125 ms 67404 KB Output is correct
42 Correct 110 ms 68784 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48976 KB Output is correct
2 Correct 21 ms 48976 KB Output is correct
3 Correct 22 ms 48976 KB Output is correct
4 Correct 21 ms 47440 KB Output is correct
5 Correct 26 ms 47440 KB Output is correct
6 Correct 26 ms 47332 KB Output is correct
7 Correct 26 ms 47432 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 27 ms 47308 KB Output is correct
10 Correct 25 ms 47260 KB Output is correct
11 Correct 25 ms 47440 KB Output is correct
12 Correct 26 ms 47340 KB Output is correct
13 Correct 24 ms 47696 KB Output is correct
14 Correct 28 ms 47572 KB Output is correct
15 Correct 28 ms 47696 KB Output is correct
16 Correct 24 ms 47688 KB Output is correct
17 Correct 23 ms 49512 KB Output is correct
18 Correct 23 ms 47696 KB Output is correct
19 Correct 25 ms 47824 KB Output is correct
20 Correct 26 ms 47696 KB Output is correct
21 Correct 29 ms 47696 KB Output is correct
22 Correct 157 ms 61512 KB Output is correct
23 Correct 164 ms 62044 KB Output is correct
24 Correct 236 ms 63228 KB Output is correct
25 Correct 342 ms 69200 KB Output is correct
26 Correct 167 ms 61768 KB Output is correct
27 Correct 324 ms 69192 KB Output is correct
28 Correct 330 ms 69248 KB Output is correct
29 Correct 152 ms 60744 KB Output is correct
30 Correct 117 ms 60744 KB Output is correct
31 Correct 137 ms 61756 KB Output is correct
32 Correct 283 ms 69960 KB Output is correct
33 Correct 155 ms 62536 KB Output is correct
34 Correct 18 ms 48976 KB Output is correct
35 Correct 16 ms 48976 KB Output is correct
36 Correct 24 ms 48976 KB Output is correct
37 Correct 22 ms 48976 KB Output is correct
38 Correct 23 ms 47696 KB Output is correct
39 Correct 23 ms 47696 KB Output is correct
40 Correct 21 ms 49488 KB Output is correct
41 Correct 112 ms 62416 KB Output is correct
42 Correct 136 ms 63316 KB Output is correct
43 Correct 283 ms 69972 KB Output is correct
44 Correct 118 ms 60832 KB Output is correct
45 Correct 130 ms 69192 KB Output is correct
46 Correct 130 ms 67400 KB Output is correct
47 Correct 112 ms 67656 KB Output is correct
48 Correct 116 ms 67016 KB Output is correct
49 Correct 120 ms 67400 KB Output is correct
50 Correct 132 ms 67144 KB Output is correct
51 Correct 758 ms 149320 KB Output is correct
52 Correct 773 ms 150856 KB Output is correct
53 Correct 639 ms 149828 KB Output is correct
54 Correct 621 ms 149064 KB Output is correct
55 Correct 652 ms 148548 KB Output is correct
56 Correct 113 ms 53320 KB Output is correct
57 Correct 108 ms 55112 KB Output is correct
58 Correct 154 ms 68424 KB Output is correct
59 Correct 167 ms 68424 KB Output is correct
60 Correct 132 ms 67912 KB Output is correct
61 Correct 150 ms 67912 KB Output is correct
62 Correct 113 ms 65864 KB Output is correct
63 Correct 129 ms 69300 KB Output is correct
64 Correct 143 ms 68472 KB Output is correct
65 Correct 152 ms 66588 KB Output is correct
66 Correct 159 ms 67032 KB Output is correct
67 Correct 146 ms 67400 KB Output is correct
68 Correct 157 ms 66120 KB Output is correct
69 Correct 148 ms 68232 KB Output is correct
70 Correct 150 ms 68732 KB Output is correct
71 Correct 151 ms 69028 KB Output is correct
72 Correct 142 ms 69192 KB Output is correct
73 Correct 143 ms 67668 KB Output is correct
74 Correct 113 ms 67144 KB Output is correct
75 Correct 125 ms 67404 KB Output is correct
76 Correct 110 ms 68784 KB Output is correct
77 Correct 894 ms 145988 KB Output is correct
78 Correct 805 ms 147364 KB Output is correct
79 Correct 779 ms 153840 KB Output is correct
80 Correct 744 ms 152800 KB Output is correct
81 Correct 722 ms 150192 KB Output is correct
82 Correct 748 ms 151200 KB Output is correct
83 Correct 898 ms 147424 KB Output is correct
84 Correct 924 ms 147528 KB Output is correct
85 Correct 931 ms 147272 KB Output is correct
86 Correct 812 ms 145500 KB Output is correct
87 Correct 842 ms 143836 KB Output is correct
88 Correct 732 ms 150204 KB Output is correct