oj.uz

Submission #915443

# Submission time Handle Problem Language Result Execution time Memory
915443 2024-01-23T23:06:54 Z SalihSahin Osumnjičeni (COCI21_osumnjiceni) C++14
60 / 110
 1000 ms 69224 KB 
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 998244353;

struct SEGT{
    vector<int> tree, lazy;

    void init(int n){
        tree.assign(4*n, 0);
        lazy.assign(4*n, 0);
    }

    void push(int ind){
        if(lazy[ind]){
            tree[ind*2] += lazy[ind];
            tree[ind*2+1] += lazy[ind];
            lazy[ind*2] += lazy[ind];
            lazy[ind*2+1] += lazy[ind];
        }
        lazy[ind] = 0;
    }

    void update(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l >= ql && r <= qr){
            tree[ind] += val;
            lazy[ind] += val;
        }
        else{
            push(ind);
            int m = (l + r)/2;

            update(ind*2, l, m, ql, qr, val);
            update(ind*2+1, m+1, r, ql, qr, val);
            tree[ind] = max(tree[ind*2], tree[ind*2+1]);
        }
    }

    int query(int ind, int l, int r, int ql, int qr){
        if(l > r || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            push(ind);
            int m = (l + r)/2;

            return max(query(ind*2, l, m, ql, qr),  query(ind*2+1, m+1, r, ql, qr));
        }
    }
};

int main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    pair<int, int> a[n];
    set<int> ste;

    for(int i = 0; i < n; i++){
        cin>>a[i].first>>a[i].second;
        ste.insert(a[i].first);
        ste.insert(a[i].second);
    }

    map<int, int> conv;
    int val = 1;
    for(auto itr: ste){
        conv[itr] = val;
        val++;
    }
    for(int i = 0; i < n; i++){
        a[i] = mp(conv[a[i].first], conv[a[i].second]);
    }
    int N = val + 5;
    
    SEGT seg;
    seg.init(N);
    int go[n];
    int need = 0;
    int r = 0;
    for(int l = 0; l < n; l++){
        while(r < n && !need){
            int x = seg.query(1, 1, N, a[r].first, a[r].second);
            if(!x){
                seg.update(1, 1, N, a[r].first, a[r].second, 1);
                r++;
            }
            else{
                need = x;
            }
        }

        go[l] = r;
        if(r < n && !(a[l].second < a[r].first || a[r].second < a[l].first)) need--;
        seg.update(1, 1, N, a[l].first, a[l].second, -1);
    }

    int K = 18;
    int lift[K][n+1];
    for(int i = 0; i < n; i++){
        lift[0][i] = go[i];
    }
    lift[0][n] = n;
    for(int i = 1; i < K; i++){
        for(int j = 0; j <= n; j++){
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }

    int q, ans, lq, rq;
    cin>>q;
    while(q--){
        cin>>lq>>rq;
        lq--, rq--;

        ans = 1;

        for(int i = K-1; i >= 0; i--){
            if(lift[i][lq] <= rq){
                lq = lift[i][lq];
                ans += (1 << i);
            }
        }

        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 66044 KB Output is correct
2 Correct 806 ms 65292 KB Output is correct
3 Correct 746 ms 65324 KB Output is correct
4 Correct 729 ms 66144 KB Output is correct
5 Correct 847 ms 69224 KB Output is correct
6 Correct 52 ms 17368 KB Output is correct
7 Correct 53 ms 17692 KB Output is correct
8 Correct 57 ms 17996 KB Output is correct
9 Correct 63 ms 18260 KB Output is correct
10 Correct 68 ms 17592 KB Output is correct
11 Correct 492 ms 67604 KB Output is correct
12 Correct 422 ms 63444 KB Output is correct
13 Correct 441 ms 63096 KB Output is correct
14 Correct 540 ms 67512 KB Output is correct
15 Correct 483 ms 65764 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 52 ms 18404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2140 KB Output is correct
2 Correct 16 ms 2140 KB Output is correct
3 Correct 16 ms 2080 KB Output is correct
4 Correct 18 ms 2136 KB Output is correct
5 Correct 16 ms 1996 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 8 ms 860 KB Output is correct
9 Correct 8 ms 904 KB Output is correct
10 Correct 9 ms 860 KB Output is correct
11 Correct 13 ms 2232 KB Output is correct
12 Correct 12 ms 2128 KB Output is correct
13 Correct 12 ms 2140 KB Output is correct
14 Correct 13 ms 2136 KB Output is correct
15 Correct 13 ms 2140 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 8 ms 860 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2140 KB Output is correct
2 Correct 16 ms 2140 KB Output is correct
3 Correct 16 ms 2080 KB Output is correct
4 Correct 18 ms 2136 KB Output is correct
5 Correct 16 ms 1996 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 8 ms 860 KB Output is correct
9 Correct 8 ms 904 KB Output is correct
10 Correct 9 ms 860 KB Output is correct
11 Correct 13 ms 2232 KB Output is correct
12 Correct 12 ms 2128 KB Output is correct
13 Correct 12 ms 2140 KB Output is correct
14 Correct 13 ms 2136 KB Output is correct
15 Correct 13 ms 2140 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 8 ms 860 KB Output is correct
18 Correct 278 ms 4496 KB Output is correct
19 Correct 251 ms 3848 KB Output is correct
20 Correct 273 ms 4376 KB Output is correct
21 Correct 252 ms 3924 KB Output is correct
22 Correct 265 ms 3996 KB Output is correct
23 Correct 254 ms 2852 KB Output is correct
24 Correct 257 ms 2984 KB Output is correct
25 Correct 272 ms 3208 KB Output is correct
26 Correct 253 ms 2976 KB Output is correct
27 Correct 255 ms 2788 KB Output is correct
28 Correct 235 ms 3640 KB Output is correct
29 Correct 261 ms 3668 KB Output is correct
30 Correct 252 ms 3768 KB Output is correct
31 Correct 246 ms 3668 KB Output is correct
32 Correct 247 ms 3920 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 248 ms 2760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 69212 KB Output is correct
2 Correct 792 ms 67804 KB Output is correct
3 Correct 729 ms 63272 KB Output is correct
4 Correct 782 ms 62620 KB Output is correct
5 Correct 764 ms 64572 KB Output is correct
6 Correct 48 ms 17664 KB Output is correct
7 Correct 57 ms 17488 KB Output is correct
8 Correct 58 ms 17612 KB Output is correct
9 Correct 62 ms 17588 KB Output is correct
10 Correct 72 ms 18772 KB Output is correct
11 Correct 462 ms 63132 KB Output is correct
12 Correct 552 ms 68944 KB Output is correct
13 Correct 501 ms 62856 KB Output is correct
14 Correct 479 ms 64740 KB Output is correct
15 Correct 552 ms 68572 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 49 ms 17884 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 66044 KB Output is correct
2 Correct 806 ms 65292 KB Output is correct
3 Correct 746 ms 65324 KB Output is correct
4 Correct 729 ms 66144 KB Output is correct
5 Correct 847 ms 69224 KB Output is correct
6 Correct 52 ms 17368 KB Output is correct
7 Correct 53 ms 17692 KB Output is correct
8 Correct 57 ms 17996 KB Output is correct
9 Correct 63 ms 18260 KB Output is correct
10 Correct 68 ms 17592 KB Output is correct
11 Correct 492 ms 67604 KB Output is correct
12 Correct 422 ms 63444 KB Output is correct
13 Correct 441 ms 63096 KB Output is correct
14 Correct 540 ms 67512 KB Output is correct
15 Correct 483 ms 65764 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 52 ms 18404 KB Output is correct
18 Correct 17 ms 2140 KB Output is correct
19 Correct 16 ms 2140 KB Output is correct
20 Correct 16 ms 2080 KB Output is correct
21 Correct 18 ms 2136 KB Output is correct
22 Correct 16 ms 1996 KB Output is correct
23 Correct 8 ms 860 KB Output is correct
24 Correct 8 ms 860 KB Output is correct
25 Correct 8 ms 860 KB Output is correct
26 Correct 8 ms 904 KB Output is correct
27 Correct 9 ms 860 KB Output is correct
28 Correct 13 ms 2232 KB Output is correct
29 Correct 12 ms 2128 KB Output is correct
30 Correct 12 ms 2140 KB Output is correct
31 Correct 13 ms 2136 KB Output is correct
32 Correct 13 ms 2140 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 8 ms 860 KB Output is correct
35 Correct 278 ms 4496 KB Output is correct
36 Correct 251 ms 3848 KB Output is correct
37 Correct 273 ms 4376 KB Output is correct
38 Correct 252 ms 3924 KB Output is correct
39 Correct 265 ms 3996 KB Output is correct
40 Correct 254 ms 2852 KB Output is correct
41 Correct 257 ms 2984 KB Output is correct
42 Correct 272 ms 3208 KB Output is correct
43 Correct 253 ms 2976 KB Output is correct
44 Correct 255 ms 2788 KB Output is correct
45 Correct 235 ms 3640 KB Output is correct
46 Correct 261 ms 3668 KB Output is correct
47 Correct 252 ms 3768 KB Output is correct
48 Correct 246 ms 3668 KB Output is correct
49 Correct 247 ms 3920 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 248 ms 2760 KB Output is correct
52 Correct 889 ms 69212 KB Output is correct
53 Correct 792 ms 67804 KB Output is correct
54 Correct 729 ms 63272 KB Output is correct
55 Correct 782 ms 62620 KB Output is correct
56 Correct 764 ms 64572 KB Output is correct
57 Correct 48 ms 17664 KB Output is correct
58 Correct 57 ms 17488 KB Output is correct
59 Correct 58 ms 17612 KB Output is correct
60 Correct 62 ms 17588 KB Output is correct
61 Correct 72 ms 18772 KB Output is correct
62 Correct 462 ms 63132 KB Output is correct
63 Correct 552 ms 68944 KB Output is correct
64 Correct 501 ms 62856 KB Output is correct
65 Correct 479 ms 64740 KB Output is correct
66 Correct 552 ms 68572 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 49 ms 17884 KB Output is correct
69 Execution timed out 1053 ms 66648 KB Time limit exceeded
70 Halted 0 ms 0 KB -