oj.uz

Submission #863057

# Submission time Handle Problem Language Result Execution time Memory
863057 2023-10-19T14:19:11 Z 3omar_ahmed Osumnjičeni (COCI21_osumnjiceni) C++17
30 / 110
 1000 ms 38912 KB 
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    int n;
    cin >> n;
    n += 1;
    vector < pair < int , int >> a(n);
    for(int i = 0 ; i + 1 < n ; i++) {
        cin >> a[i].first >> a[i].second;
    }    
    a[n - 1] = {1, n};
    vector < vector < int >> nxt(20, vector < int > (n + 1, -1));
    nxt[0][n - 1] = n - 1;
    for(int i = n - 2 ; i >= 0 ; i--) {
        nxt[0][i] = nxt[0][i + 1];
        for(int j = i + 1 ; j < n ; j++) {
            int l = max(a[i].first, a[j].first);
            int r = min(a[i].second, a[j].second);
            if(l <= r) nxt[0][i] = min(nxt[0][i], j - 1);
        }
    }

    for(int i = 1 ; i < 20 ; i++) {
        for(int j = 0 ; j < n ; j++) {
            if(nxt[i - 1][j] != -1)
                nxt[i][j] = nxt[i - 1][nxt[i - 1][j] + 1];
        }
    }

    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        l -= 1, r -= 1;
        int ans = 0;
        for(int i = 19 ; i >= 0 ; i--) {
            if(nxt[i][l] <= r && nxt[i][l] != -1) {
                ans += (1ll << i);
                l = nxt[i][l] + 1;
            }
        }
        ans += (l <= r);
        cout << ans << endl;
    }
    return 0 ;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 37460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1368 KB Output is correct
2 Correct 42 ms 1404 KB Output is correct
3 Correct 43 ms 1372 KB Output is correct
4 Correct 48 ms 1460 KB Output is correct
5 Correct 41 ms 1368 KB Output is correct
6 Correct 21 ms 1476 KB Output is correct
7 Correct 28 ms 1416 KB Output is correct
8 Correct 28 ms 1472 KB Output is correct
9 Correct 35 ms 1424 KB Output is correct
10 Correct 22 ms 1404 KB Output is correct
11 Correct 27 ms 1368 KB Output is correct
12 Correct 24 ms 1148 KB Output is correct
13 Correct 18 ms 1372 KB Output is correct
14 Correct 15 ms 1372 KB Output is correct
15 Correct 16 ms 1368 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 19 ms 1368 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1368 KB Output is correct
2 Correct 42 ms 1404 KB Output is correct
3 Correct 43 ms 1372 KB Output is correct
4 Correct 48 ms 1460 KB Output is correct
5 Correct 41 ms 1368 KB Output is correct
6 Correct 21 ms 1476 KB Output is correct
7 Correct 28 ms 1416 KB Output is correct
8 Correct 28 ms 1472 KB Output is correct
9 Correct 35 ms 1424 KB Output is correct
10 Correct 22 ms 1404 KB Output is correct
11 Correct 27 ms 1368 KB Output is correct
12 Correct 24 ms 1148 KB Output is correct
13 Correct 18 ms 1372 KB Output is correct
14 Correct 15 ms 1372 KB Output is correct
15 Correct 16 ms 1368 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 19 ms 1368 KB Output is correct
18 Correct 109 ms 3956 KB Output is correct
19 Correct 98 ms 3552 KB Output is correct
20 Correct 112 ms 3896 KB Output is correct
21 Correct 99 ms 3668 KB Output is correct
22 Correct 108 ms 3808 KB Output is correct
23 Correct 72 ms 3592 KB Output is correct
24 Correct 94 ms 3884 KB Output is correct
25 Correct 83 ms 3884 KB Output is correct
26 Correct 80 ms 3876 KB Output is correct
27 Correct 72 ms 3668 KB Output is correct
28 Correct 60 ms 3412 KB Output is correct
29 Correct 51 ms 3432 KB Output is correct
30 Correct 56 ms 3228 KB Output is correct
31 Correct 66 ms 3412 KB Output is correct
32 Correct 61 ms 3272 KB Output is correct
33 Correct 0 ms 448 KB Output is correct
34 Correct 59 ms 3672 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 38912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 37460 KB Time limit exceeded
2 Halted 0 ms 0 KB -