oj.uz

Submission #725072

# Submission time Handle Problem Language Result Execution time Memory
725072 2023-04-16T18:25:27 Z TahirAliyev Osumnjičeni (COCI21_osumnjiceni) C++17
110 / 110
 760 ms 33656 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;
 
#define ll long long int
#define oo 1e18 + 5
#define pii pair<int, int>

const int MAX = 2e5 + 5;
const int LOGMAX = 20;

pii arr[MAX]; 
int par[LOGMAX + 1][MAX];

bool isOverlap(pii a, pii b){
    return a.second >= b.first && b.second >= a.first;
}

int binLift(int l, int r){
    int ans = 1;
    for(int j = LOGMAX; j >= 0; j--){
        if(par[j][l] <= r){
            l = par[j][l];
            ans += (1 << j);
        }
    }
    return ans;
}

int main(){
    int n, q; cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }
    set<pii> s;
    int t = 0;
    for (int i = 0; i < n; i++)
    {
        while(!s.empty()){
            auto itr = s.upper_bound({arr[i].first, oo});
            auto itr2 = s.upper_bound({arr[i].second, oo});
            if(itr != s.begin()) itr--;
            if(itr2 != s.begin()) itr2--;
            if(isOverlap(*itr, arr[i]) || isOverlap(*itr2, arr[i])){
                par[0][t] = i;
                s.erase(arr[t]);
                t++;
            }
            else break;
        }
        s.insert(arr[i]);
    }
    for (int k = t; k <= n; k++)
    {
        par[0][k] = n;
    }
    for (int j = 1; j <= LOGMAX; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        l--;r--;
        cout << binLift(l, r) << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 21168 KB Output is correct
2 Correct 163 ms 20572 KB Output is correct
3 Correct 161 ms 20608 KB Output is correct
4 Correct 164 ms 20784 KB Output is correct
5 Correct 183 ms 21556 KB Output is correct
6 Correct 150 ms 19956 KB Output is correct
7 Correct 159 ms 20136 KB Output is correct
8 Correct 157 ms 20416 KB Output is correct
9 Correct 174 ms 20812 KB Output is correct
10 Correct 158 ms 20204 KB Output is correct
11 Correct 246 ms 30384 KB Output is correct
12 Correct 258 ms 28496 KB Output is correct
13 Correct 250 ms 28468 KB Output is correct
14 Correct 283 ms 26556 KB Output is correct
15 Correct 253 ms 24496 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 156 ms 21468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1004 KB Output is correct
2 Correct 14 ms 980 KB Output is correct
3 Correct 15 ms 988 KB Output is correct
4 Correct 14 ms 980 KB Output is correct
5 Correct 13 ms 980 KB Output is correct
6 Correct 14 ms 1032 KB Output is correct
7 Correct 13 ms 944 KB Output is correct
8 Correct 14 ms 1108 KB Output is correct
9 Correct 14 ms 948 KB Output is correct
10 Correct 13 ms 1000 KB Output is correct
11 Correct 14 ms 1196 KB Output is correct
12 Correct 13 ms 1108 KB Output is correct
13 Correct 13 ms 1108 KB Output is correct
14 Correct 14 ms 1068 KB Output is correct
15 Correct 15 ms 1052 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 14 ms 1012 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1004 KB Output is correct
2 Correct 14 ms 980 KB Output is correct
3 Correct 15 ms 988 KB Output is correct
4 Correct 14 ms 980 KB Output is correct
5 Correct 13 ms 980 KB Output is correct
6 Correct 14 ms 1032 KB Output is correct
7 Correct 13 ms 944 KB Output is correct
8 Correct 14 ms 1108 KB Output is correct
9 Correct 14 ms 948 KB Output is correct
10 Correct 13 ms 1000 KB Output is correct
11 Correct 14 ms 1196 KB Output is correct
12 Correct 13 ms 1108 KB Output is correct
13 Correct 13 ms 1108 KB Output is correct
14 Correct 14 ms 1068 KB Output is correct
15 Correct 15 ms 1052 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 14 ms 1012 KB Output is correct
18 Correct 369 ms 3636 KB Output is correct
19 Correct 339 ms 3392 KB Output is correct
20 Correct 379 ms 3612 KB Output is correct
21 Correct 361 ms 3444 KB Output is correct
22 Correct 366 ms 3520 KB Output is correct
23 Correct 334 ms 3428 KB Output is correct
24 Correct 348 ms 3600 KB Output is correct
25 Correct 369 ms 3672 KB Output is correct
26 Correct 348 ms 3556 KB Output is correct
27 Correct 341 ms 3288 KB Output is correct
28 Correct 318 ms 3124 KB Output is correct
29 Correct 351 ms 3296 KB Output is correct
30 Correct 336 ms 3232 KB Output is correct
31 Correct 333 ms 3000 KB Output is correct
32 Correct 327 ms 3164 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 332 ms 3292 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 22184 KB Output is correct
2 Correct 166 ms 21196 KB Output is correct
3 Correct 158 ms 20104 KB Output is correct
4 Correct 151 ms 19836 KB Output is correct
5 Correct 158 ms 20300 KB Output is correct
6 Correct 148 ms 20168 KB Output is correct
7 Correct 150 ms 19836 KB Output is correct
8 Correct 172 ms 20084 KB Output is correct
9 Correct 175 ms 19904 KB Output is correct
10 Correct 178 ms 21304 KB Output is correct
11 Correct 231 ms 28164 KB Output is correct
12 Correct 251 ms 31064 KB Output is correct
13 Correct 229 ms 28156 KB Output is correct
14 Correct 257 ms 24592 KB Output is correct
15 Correct 320 ms 26648 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 154 ms 20648 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 21168 KB Output is correct
2 Correct 163 ms 20572 KB Output is correct
3 Correct 161 ms 20608 KB Output is correct
4 Correct 164 ms 20784 KB Output is correct
5 Correct 183 ms 21556 KB Output is correct
6 Correct 150 ms 19956 KB Output is correct
7 Correct 159 ms 20136 KB Output is correct
8 Correct 157 ms 20416 KB Output is correct
9 Correct 174 ms 20812 KB Output is correct
10 Correct 158 ms 20204 KB Output is correct
11 Correct 246 ms 30384 KB Output is correct
12 Correct 258 ms 28496 KB Output is correct
13 Correct 250 ms 28468 KB Output is correct
14 Correct 283 ms 26556 KB Output is correct
15 Correct 253 ms 24496 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 156 ms 21468 KB Output is correct
18 Correct 17 ms 1004 KB Output is correct
19 Correct 14 ms 980 KB Output is correct
20 Correct 15 ms 988 KB Output is correct
21 Correct 14 ms 980 KB Output is correct
22 Correct 13 ms 980 KB Output is correct
23 Correct 14 ms 1032 KB Output is correct
24 Correct 13 ms 944 KB Output is correct
25 Correct 14 ms 1108 KB Output is correct
26 Correct 14 ms 948 KB Output is correct
27 Correct 13 ms 1000 KB Output is correct
28 Correct 14 ms 1196 KB Output is correct
29 Correct 13 ms 1108 KB Output is correct
30 Correct 13 ms 1108 KB Output is correct
31 Correct 14 ms 1068 KB Output is correct
32 Correct 15 ms 1052 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 14 ms 1012 KB Output is correct
35 Correct 369 ms 3636 KB Output is correct
36 Correct 339 ms 3392 KB Output is correct
37 Correct 379 ms 3612 KB Output is correct
38 Correct 361 ms 3444 KB Output is correct
39 Correct 366 ms 3520 KB Output is correct
40 Correct 334 ms 3428 KB Output is correct
41 Correct 348 ms 3600 KB Output is correct
42 Correct 369 ms 3672 KB Output is correct
43 Correct 348 ms 3556 KB Output is correct
44 Correct 341 ms 3288 KB Output is correct
45 Correct 318 ms 3124 KB Output is correct
46 Correct 351 ms 3296 KB Output is correct
47 Correct 336 ms 3232 KB Output is correct
48 Correct 333 ms 3000 KB Output is correct
49 Correct 327 ms 3164 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 332 ms 3292 KB Output is correct
52 Correct 168 ms 22184 KB Output is correct
53 Correct 166 ms 21196 KB Output is correct
54 Correct 158 ms 20104 KB Output is correct
55 Correct 151 ms 19836 KB Output is correct
56 Correct 158 ms 20300 KB Output is correct
57 Correct 148 ms 20168 KB Output is correct
58 Correct 150 ms 19836 KB Output is correct
59 Correct 172 ms 20084 KB Output is correct
60 Correct 175 ms 19904 KB Output is correct
61 Correct 178 ms 21304 KB Output is correct
62 Correct 231 ms 28164 KB Output is correct
63 Correct 251 ms 31064 KB Output is correct
64 Correct 229 ms 28156 KB Output is correct
65 Correct 257 ms 24592 KB Output is correct
66 Correct 320 ms 26648 KB Output is correct
67 Correct 1 ms 340 KB Output is correct
68 Correct 154 ms 20648 KB Output is correct
69 Correct 739 ms 24248 KB Output is correct
70 Correct 716 ms 25368 KB Output is correct
71 Correct 709 ms 23500 KB Output is correct
72 Correct 662 ms 24624 KB Output is correct
73 Correct 712 ms 24432 KB Output is correct
74 Correct 712 ms 25572 KB Output is correct
75 Correct 693 ms 24060 KB Output is correct
76 Correct 690 ms 25608 KB Output is correct
77 Correct 728 ms 23676 KB Output is correct
78 Correct 760 ms 24164 KB Output is correct
79 Correct 690 ms 33656 KB Output is correct
80 Correct 681 ms 31204 KB Output is correct
81 Correct 736 ms 31076 KB Output is correct
82 Correct 697 ms 27848 KB Output is correct
83 Correct 681 ms 26624 KB Output is correct
84 Correct 1 ms 340 KB Output is correct
85 Correct 547 ms 23812 KB Output is correct