oj.uz

Submission #915626

# Submission time Handle Problem Language Result Execution time Memory
915626 2024-01-24T11:53:59 Z SalihSahin Osumnjičeni (COCI21_osumnjiceni) C++14
110 / 110
 561 ms 31492 KB 
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 998244353;

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

    for(int i = 0; i < n; i++){
        cin>>a[i].first>>a[i].second;
    }
    int K = 18, r = 0;
    
    set<pair<int, int> > op;

    int lift[K][n+1];
    for(int l = 0; l < n; l++){
        while(r < n){
            bool ok = 1;
            if(op.size()){
                auto it = op.lower_bound(a[r]);
                if(it != op.end() && (*it).first <= a[r].second) ok = 0;
                if(it != op.begin()){
                    it--;
                    if((*it).second >= a[r].first) ok = 0;
                }
            }

            if(ok){
                op.insert(a[r]);
                r++;
            }
            else break;
        }

        lift[0][l] = r;
        op.erase(a[l]);
        //cout<<l<<" "<<r<<endl;
    }


    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 46 ms 15188 KB Output is correct
2 Correct 46 ms 18584 KB Output is correct
3 Correct 46 ms 18772 KB Output is correct
4 Correct 47 ms 19024 KB Output is correct
5 Correct 50 ms 19768 KB Output is correct
6 Correct 43 ms 18100 KB Output is correct
7 Correct 45 ms 18384 KB Output is correct
8 Correct 47 ms 18396 KB Output is correct
9 Correct 51 ms 18856 KB Output is correct
10 Correct 54 ms 18260 KB Output is correct
11 Correct 157 ms 27944 KB Output is correct
12 Correct 141 ms 26436 KB Output is correct
13 Correct 145 ms 26272 KB Output is correct
14 Correct 138 ms 24240 KB Output is correct
15 Correct 128 ms 22224 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 45 ms 19220 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 11 ms 860 KB Output is correct
3 Correct 8 ms 856 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 9 ms 860 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 8 ms 856 KB Output is correct
8 Correct 8 ms 856 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 9 ms 1112 KB Output is correct
12 Correct 9 ms 1108 KB Output is correct
13 Correct 9 ms 1108 KB Output is correct
14 Correct 9 ms 1112 KB Output is correct
15 Correct 9 ms 1024 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 980 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 11 ms 860 KB Output is correct
3 Correct 8 ms 856 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 9 ms 860 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 8 ms 856 KB Output is correct
8 Correct 8 ms 856 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 9 ms 1112 KB Output is correct
12 Correct 9 ms 1108 KB Output is correct
13 Correct 9 ms 1108 KB Output is correct
14 Correct 9 ms 1112 KB Output is correct
15 Correct 9 ms 1024 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 980 KB Output is correct
18 Correct 266 ms 3412 KB Output is correct
19 Correct 244 ms 3416 KB Output is correct
20 Correct 289 ms 3664 KB Output is correct
21 Correct 250 ms 3296 KB Output is correct
22 Correct 262 ms 3512 KB Output is correct
23 Correct 253 ms 3412 KB Output is correct
24 Correct 258 ms 3520 KB Output is correct
25 Correct 266 ms 3472 KB Output is correct
26 Correct 265 ms 3392 KB Output is correct
27 Correct 246 ms 3156 KB Output is correct
28 Correct 258 ms 3148 KB Output is correct
29 Correct 252 ms 3216 KB Output is correct
30 Correct 250 ms 3156 KB Output is correct
31 Correct 249 ms 2956 KB Output is correct
32 Correct 239 ms 3016 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 267 ms 3156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15952 KB Output is correct
2 Correct 49 ms 19312 KB Output is correct
3 Correct 51 ms 18220 KB Output is correct
4 Correct 47 ms 17948 KB Output is correct
5 Correct 47 ms 18592 KB Output is correct
6 Correct 44 ms 18268 KB Output is correct
7 Correct 47 ms 17968 KB Output is correct
8 Correct 50 ms 18000 KB Output is correct
9 Correct 49 ms 18000 KB Output is correct
10 Correct 59 ms 19400 KB Output is correct
11 Correct 142 ms 26196 KB Output is correct
12 Correct 152 ms 28496 KB Output is correct
13 Correct 147 ms 26172 KB Output is correct
14 Correct 140 ms 22356 KB Output is correct
15 Correct 157 ms 24272 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 45 ms 18500 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15188 KB Output is correct
2 Correct 46 ms 18584 KB Output is correct
3 Correct 46 ms 18772 KB Output is correct
4 Correct 47 ms 19024 KB Output is correct
5 Correct 50 ms 19768 KB Output is correct
6 Correct 43 ms 18100 KB Output is correct
7 Correct 45 ms 18384 KB Output is correct
8 Correct 47 ms 18396 KB Output is correct
9 Correct 51 ms 18856 KB Output is correct
10 Correct 54 ms 18260 KB Output is correct
11 Correct 157 ms 27944 KB Output is correct
12 Correct 141 ms 26436 KB Output is correct
13 Correct 145 ms 26272 KB Output is correct
14 Correct 138 ms 24240 KB Output is correct
15 Correct 128 ms 22224 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 45 ms 19220 KB Output is correct
18 Correct 8 ms 604 KB Output is correct
19 Correct 11 ms 860 KB Output is correct
20 Correct 8 ms 856 KB Output is correct
21 Correct 8 ms 860 KB Output is correct
22 Correct 9 ms 860 KB Output is correct
23 Correct 8 ms 860 KB Output is correct
24 Correct 8 ms 856 KB Output is correct
25 Correct 8 ms 856 KB Output is correct
26 Correct 8 ms 860 KB Output is correct
27 Correct 8 ms 860 KB Output is correct
28 Correct 9 ms 1112 KB Output is correct
29 Correct 9 ms 1108 KB Output is correct
30 Correct 9 ms 1108 KB Output is correct
31 Correct 9 ms 1112 KB Output is correct
32 Correct 9 ms 1024 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 8 ms 980 KB Output is correct
35 Correct 266 ms 3412 KB Output is correct
36 Correct 244 ms 3416 KB Output is correct
37 Correct 289 ms 3664 KB Output is correct
38 Correct 250 ms 3296 KB Output is correct
39 Correct 262 ms 3512 KB Output is correct
40 Correct 253 ms 3412 KB Output is correct
41 Correct 258 ms 3520 KB Output is correct
42 Correct 266 ms 3472 KB Output is correct
43 Correct 265 ms 3392 KB Output is correct
44 Correct 246 ms 3156 KB Output is correct
45 Correct 258 ms 3148 KB Output is correct
46 Correct 252 ms 3216 KB Output is correct
47 Correct 250 ms 3156 KB Output is correct
48 Correct 249 ms 2956 KB Output is correct
49 Correct 239 ms 3016 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 267 ms 3156 KB Output is correct
52 Correct 52 ms 15952 KB Output is correct
53 Correct 49 ms 19312 KB Output is correct
54 Correct 51 ms 18220 KB Output is correct
55 Correct 47 ms 17948 KB Output is correct
56 Correct 47 ms 18592 KB Output is correct
57 Correct 44 ms 18268 KB Output is correct
58 Correct 47 ms 17968 KB Output is correct
59 Correct 50 ms 18000 KB Output is correct
60 Correct 49 ms 18000 KB Output is correct
61 Correct 59 ms 19400 KB Output is correct
62 Correct 142 ms 26196 KB Output is correct
63 Correct 152 ms 28496 KB Output is correct
64 Correct 147 ms 26172 KB Output is correct
65 Correct 140 ms 22356 KB Output is correct
66 Correct 157 ms 24272 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 45 ms 18500 KB Output is correct
69 Correct 416 ms 22276 KB Output is correct
70 Correct 451 ms 23360 KB Output is correct
71 Correct 518 ms 21092 KB Output is correct
72 Correct 400 ms 22352 KB Output is correct
73 Correct 526 ms 22244 KB Output is correct
74 Correct 561 ms 23288 KB Output is correct
75 Correct 477 ms 21640 KB Output is correct
76 Correct 493 ms 23500 KB Output is correct
77 Correct 385 ms 21588 KB Output is correct
78 Correct 385 ms 21980 KB Output is correct
79 Correct 447 ms 31492 KB Output is correct
80 Correct 411 ms 29008 KB Output is correct
81 Correct 420 ms 29136 KB Output is correct
82 Correct 404 ms 25492 KB Output is correct
83 Correct 398 ms 24368 KB Output is correct
84 Correct 0 ms 344 KB Output is correct
85 Correct 316 ms 22224 KB Output is correct