oj.uz

Submission #826124

# Submission time Handle Problem Language Result Execution time Memory
826124 2023-08-15T10:32:59 Z model_code Curtains (NOI23_curtains) C++17
100 / 100
 899 ms 75700 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 500000
#define MAXM 500000
#define MAXQ 500000

#define DEBUG 0

typedef pair<int,int> pi;

bool endpoint_cmp(pi A, pi B){
    return A.second < B.second;
}

int N, M, Q;
int L[MAXM+5], R[MAXM+5], S[MAXQ+5], E[MAXQ+5];
int ans[MAXQ+5]; 

struct node{
    node *left = nullptr, *right = nullptr;
    int s, e, rend, act = 0;
    
    int lazy_left = -1, lazy_right = -1;

    node (int _s, int _e){
        s = _s;
        e = _e;
        if (s != e){
            left = new node(s,(s+e)/2);
            right = new node((s+e)/2+1,e);
        }
        else rend = s-1;
    }

    void update_lazy(int ul, int ur){
        if (lazy_left == -1 || ul <= lazy_left){
            lazy_left = ul;
            lazy_right = ur;
        }
        else if (ul <= lazy_right){
            lazy_right = ur;
        }
    }

    void propagate(){
        if (lazy_left == -1) return;
        left->update_lazy(lazy_left,lazy_right);
        right->update_lazy(lazy_left,lazy_right);
        lazy_left = lazy_right = -1;
    }

    void update(int l, int r, int ul, int ur){
        if (DEBUG) cerr << "UPDATING NODE [" << s << "," << e << "] WITH UPDATE LEFT = " << l << ", RIGHT = " << r << ", U-LEFT = " << ul << ", U-RIGHT = " << ur << '\n';
        if (l > e || r < s){
            if (DEBUG) cerr << "OUT OF RANGE\n";
            return;
        }
        if (l <= s && e <= r){
            if (DEBUG) cerr << "IN RANGE, UPDATING CURRENT L-LEFT = " << lazy_left << ", L-RIGHT = " << lazy_right << "\n";
            update_lazy(ul,ur);
            if (DEBUG) cerr << "NEW L-LEFT = " << lazy_left << ", L-RIGHT = " << lazy_right << "\n";
            return;
        }
        propagate();
        left->update(l,r,ul,ur);
        right->update(l,r,ul,ur);
    }

    pi query(int x){
        if (DEBUG){
            cerr << "QUERYING NODE [" << s << "," << e << "] AT INDEX X = " << x << "\n";
        }
        if (s == e){
            if (lazy_left != -1){
                if (rend >= lazy_left){
                    rend = max(rend,lazy_right);
                    act = 1;
                }
                lazy_left = lazy_right = -1;
            }
            if (DEBUG){
                cerr << "END QUERYING NODE [" << s << "," << e << "] AT INDEX X = " << x << "\n";
                cerr << "RETURNING FROM BASE NODE (REND = " << rend << ", ACTIVE = " << act << "}\n"; 
            }
            return pi(rend,act);
        }
        else{
            pi a;
            if (x <= (s+e)/2) a = left->query(x);
            else a = right->query(x);
            if (lazy_left != -1){
                if (a.first >= lazy_left){
                    a.first = max(a.first,lazy_right);
                    a.second = 1;
                }
            }
            if (DEBUG){
                cerr << "END QUERYING NODE [" << s << "," << e << "] AT INDEX X = " << x << "\n";
                cerr << "RETURNING FROM INTERMEDIATE NODE (REND = " << a.first << ", ACTIVE = " << a.second << "}\n";
            }
            
            return a;
        }
    }



} *root = nullptr;

struct op{
    int typ; // update = 0, query = 1
    int l, r;
    int idx; // for queries

    op(int _t, int _l, int _r, int _i){
        typ = _t, l = _l, r = _r, idx = _i;
    }

    bool operator<(const op &other)const{
        return r < other.r || (r == other.r && typ < other.typ);
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M >> Q;

    vector<op> v;

    for (int i = 1; i <= M; ++i){
        cin >> L[i] >> R[i];
        v.push_back(op(0,L[i],R[i],i));
    }

    for (int i = 1; i <= Q; ++i){
        cin >> S[i] >> E[i];
        v.push_back(op(1,S[i],E[i],i));
    }

    sort(v.begin(),v.end());

    root = new node(1,N);

    for (auto it : v){
        if (DEBUG){
            cerr << "PROCESSING OP WITH PARAMS {TYPE = " << it.typ << ", LEFT = " << it.l << ", RIGHT = " << it.r << ", INDEX = " << it.idx << "}\n";
        }
        if (it.typ == 0){
            if (DEBUG) cerr << "UPDATING\n";
            root->update(1,it.l,it.l-1,it.r);
        }
        else{
            pi far = root->query(it.l);
            if (far.first == it.r && far.second == 1) ans[it.idx] = 1;
            else ans[it.idx] = 0;
        }
    }

    for (int i = 1; i <= Q; ++i){
        if (ans[i]) cout << "YES\n";
        else cout << "NO\n";
    }

}

Subtask #1
3.0 / 3.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 3 ms 556 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 3 ms 556 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 190 ms 15732 KB Output is correct
23 Correct 188 ms 16248 KB Output is correct
24 Correct 209 ms 20908 KB Output is correct
25 Correct 372 ms 27916 KB Output is correct
26 Correct 180 ms 16104 KB Output is correct
27 Correct 358 ms 30232 KB Output is correct
28 Correct 352 ms 31668 KB Output is correct
29 Correct 156 ms 15920 KB Output is correct
30 Correct 116 ms 16188 KB Output is correct
31 Correct 133 ms 20940 KB Output is correct
32 Correct 320 ms 28004 KB Output is correct
33 Correct 108 ms 16408 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 648 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 109 ms 16136 KB Output is correct
9 Correct 129 ms 21020 KB Output is correct
10 Correct 282 ms 27880 KB Output is correct
11 Correct 111 ms 16452 KB Output is correct
12 Correct 90 ms 15100 KB Output is correct
13 Correct 88 ms 15184 KB Output is correct
14 Correct 63 ms 15096 KB Output is correct
15 Correct 64 ms 15100 KB Output is correct
16 Correct 65 ms 15028 KB Output is correct
17 Correct 64 ms 15096 KB Output is correct
18 Correct 652 ms 74392 KB Output is correct
19 Correct 601 ms 74392 KB Output is correct
20 Correct 343 ms 74136 KB Output is correct
21 Correct 350 ms 74140 KB Output is correct
22 Correct 373 ms 74136 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 3 ms 556 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 78 ms 6776 KB Output is correct
23 Correct 80 ms 6772 KB Output is correct
24 Correct 133 ms 15096 KB Output is correct
25 Correct 126 ms 15164 KB Output is correct
26 Correct 84 ms 15112 KB Output is correct
27 Correct 86 ms 15172 KB Output is correct
28 Correct 69 ms 13932 KB Output is correct
29 Correct 84 ms 14816 KB Output is correct
30 Correct 120 ms 15160 KB Output is correct
31 Correct 117 ms 15104 KB Output is correct
32 Correct 110 ms 15096 KB Output is correct
33 Correct 87 ms 15156 KB Output is correct
34 Correct 101 ms 15164 KB Output is correct
35 Correct 106 ms 15092 KB Output is correct
36 Correct 95 ms 15068 KB Output is correct
37 Correct 92 ms 15100 KB Output is correct
38 Correct 88 ms 15100 KB Output is correct
39 Correct 63 ms 15096 KB Output is correct
40 Correct 66 ms 15048 KB Output is correct
41 Correct 62 ms 15024 KB Output is correct
42 Correct 62 ms 15052 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 3 ms 556 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 190 ms 15732 KB Output is correct
23 Correct 188 ms 16248 KB Output is correct
24 Correct 209 ms 20908 KB Output is correct
25 Correct 372 ms 27916 KB Output is correct
26 Correct 180 ms 16104 KB Output is correct
27 Correct 358 ms 30232 KB Output is correct
28 Correct 352 ms 31668 KB Output is correct
29 Correct 156 ms 15920 KB Output is correct
30 Correct 116 ms 16188 KB Output is correct
31 Correct 133 ms 20940 KB Output is correct
32 Correct 320 ms 28004 KB Output is correct
33 Correct 108 ms 16408 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 2 ms 648 KB Output is correct
39 Correct 1 ms 596 KB Output is correct
40 Correct 1 ms 596 KB Output is correct
41 Correct 109 ms 16136 KB Output is correct
42 Correct 129 ms 21020 KB Output is correct
43 Correct 282 ms 27880 KB Output is correct
44 Correct 111 ms 16452 KB Output is correct
45 Correct 90 ms 15100 KB Output is correct
46 Correct 88 ms 15184 KB Output is correct
47 Correct 63 ms 15096 KB Output is correct
48 Correct 64 ms 15100 KB Output is correct
49 Correct 65 ms 15028 KB Output is correct
50 Correct 64 ms 15096 KB Output is correct
51 Correct 652 ms 74392 KB Output is correct
52 Correct 601 ms 74392 KB Output is correct
53 Correct 343 ms 74136 KB Output is correct
54 Correct 350 ms 74140 KB Output is correct
55 Correct 373 ms 74136 KB Output is correct
56 Correct 78 ms 6776 KB Output is correct
57 Correct 80 ms 6772 KB Output is correct
58 Correct 133 ms 15096 KB Output is correct
59 Correct 126 ms 15164 KB Output is correct
60 Correct 84 ms 15112 KB Output is correct
61 Correct 86 ms 15172 KB Output is correct
62 Correct 69 ms 13932 KB Output is correct
63 Correct 84 ms 14816 KB Output is correct
64 Correct 120 ms 15160 KB Output is correct
65 Correct 117 ms 15104 KB Output is correct
66 Correct 110 ms 15096 KB Output is correct
67 Correct 87 ms 15156 KB Output is correct
68 Correct 101 ms 15164 KB Output is correct
69 Correct 106 ms 15092 KB Output is correct
70 Correct 95 ms 15068 KB Output is correct
71 Correct 92 ms 15100 KB Output is correct
72 Correct 88 ms 15100 KB Output is correct
73 Correct 63 ms 15096 KB Output is correct
74 Correct 66 ms 15048 KB Output is correct
75 Correct 62 ms 15024 KB Output is correct
76 Correct 62 ms 15052 KB Output is correct
77 Correct 892 ms 74260 KB Output is correct
78 Correct 899 ms 74264 KB Output is correct
79 Correct 653 ms 75700 KB Output is correct
80 Correct 560 ms 74652 KB Output is correct
81 Correct 537 ms 73436 KB Output is correct
82 Correct 578 ms 73912 KB Output is correct
83 Correct 836 ms 74268 KB Output is correct
84 Correct 811 ms 74376 KB Output is correct
85 Correct 687 ms 74392 KB Output is correct
86 Correct 664 ms 74292 KB Output is correct
87 Correct 623 ms 74260 KB Output is correct
88 Correct 585 ms 74264 KB Output is correct