oj.uz

Submission #877889

# Submission time Handle Problem Language Result Execution time Memory
877889 2023-11-23T20:30:06 Z TahirAliyev Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1780 ms 98824 KB 
#include <bits/stdc++.h>
using namespace std;


#define ll long long int
#define pii pair<int, int>
#define oo 1e9

const int MAX = 1e6 + 6;

int n, m;
int tree[4 * MAX];
int arr[MAX];

void update(int node, int l, int r, int pos, int val){
    if(l == r){
        tree[node] = max(tree[node], val);
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid) update(2 * node, l, mid, pos, val);
    else update(2 * node + 1, mid + 1, r, pos, val);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int ask(int node, int l, int r, int ql, int qr){
    if(r < ql || qr < l) return 0;
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return max(ask(2 * node, l, mid , ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}

vector<pii> q[MAX];
int ans[MAX];
int k[MAX];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    for(int i = 1; i <= m; i++){
        int l, r, a; cin >> l >> r >> a;
        k[i] = a;
        q[r].push_back({l, i});
    }
    stack<pii> s;
    for(int r = 1; r <= n; r++){
        while(s.size() && s.top().first <= arr[r]){
            s.pop();
        }
        if(s.size()) update(1, 1, n, s.top().second, arr[r] + s.top().first);
        s.push({arr[r], r});
        for(pii l : q[r]){
            ans[l.second] = ask(1, 1, n, l.first, r);
        }
    }
    for(int i = 1; i <= m; i++){
        if(ans[i] <= k[i]) cout << "1\n";
        else cout << "0\n";
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 6 ms 29140 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29016 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29208 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 6 ms 29140 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29016 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29208 KB Output is correct
11 Correct 9 ms 29272 KB Output is correct
12 Correct 10 ms 29276 KB Output is correct
13 Correct 11 ms 29272 KB Output is correct
14 Correct 13 ms 29404 KB Output is correct
15 Correct 15 ms 29276 KB Output is correct
16 Correct 11 ms 29276 KB Output is correct
17 Correct 11 ms 29392 KB Output is correct
18 Correct 11 ms 29276 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1688 ms 97360 KB Output is correct
2 Correct 1729 ms 98824 KB Output is correct
3 Correct 1716 ms 98232 KB Output is correct
4 Correct 1679 ms 98720 KB Output is correct
5 Correct 1583 ms 92244 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 38484 KB Output is correct
2 Correct 115 ms 37844 KB Output is correct
3 Correct 109 ms 37204 KB Output is correct
4 Correct 112 ms 37204 KB Output is correct
5 Correct 110 ms 37460 KB Output is correct
6 Correct 98 ms 36524 KB Output is correct
7 Correct 97 ms 36468 KB Output is correct
8 Correct 118 ms 37096 KB Output is correct
9 Correct 69 ms 35864 KB Output is correct
10 Correct 107 ms 37068 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 6 ms 29140 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29016 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29208 KB Output is correct
11 Correct 9 ms 29272 KB Output is correct
12 Correct 10 ms 29276 KB Output is correct
13 Correct 11 ms 29272 KB Output is correct
14 Correct 13 ms 29404 KB Output is correct
15 Correct 15 ms 29276 KB Output is correct
16 Correct 11 ms 29276 KB Output is correct
17 Correct 11 ms 29392 KB Output is correct
18 Correct 11 ms 29276 KB Output is correct
19 Correct 299 ms 46076 KB Output is correct
20 Correct 331 ms 46180 KB Output is correct
21 Correct 274 ms 44788 KB Output is correct
22 Correct 300 ms 44760 KB Output is correct
23 Correct 274 ms 44788 KB Output is correct
24 Correct 250 ms 42464 KB Output is correct
25 Correct 262 ms 42628 KB Output is correct
26 Correct 272 ms 43340 KB Output is correct
27 Correct 272 ms 43604 KB Output is correct
28 Correct 275 ms 43344 KB Output is correct
29 Correct 291 ms 44116 KB Output is correct
30 Correct 289 ms 44108 KB Output is correct
31 Correct 279 ms 43992 KB Output is correct
32 Correct 292 ms 43968 KB Output is correct
33 Correct 297 ms 44112 KB Output is correct
34 Correct 251 ms 42512 KB Output is correct
35 Correct 241 ms 42320 KB Output is correct
36 Correct 237 ms 42036 KB Output is correct
37 Correct 237 ms 42068 KB Output is correct
38 Correct 248 ms 42320 KB Output is correct
39 Correct 253 ms 43200 KB Output is correct
40 Correct 240 ms 41416 KB Output is correct
41 Correct 223 ms 42192 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 6 ms 29140 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29016 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29208 KB Output is correct
11 Correct 9 ms 29272 KB Output is correct
12 Correct 10 ms 29276 KB Output is correct
13 Correct 11 ms 29272 KB Output is correct
14 Correct 13 ms 29404 KB Output is correct
15 Correct 15 ms 29276 KB Output is correct
16 Correct 11 ms 29276 KB Output is correct
17 Correct 11 ms 29392 KB Output is correct
18 Correct 11 ms 29276 KB Output is correct
19 Correct 1688 ms 97360 KB Output is correct
20 Correct 1729 ms 98824 KB Output is correct
21 Correct 1716 ms 98232 KB Output is correct
22 Correct 1679 ms 98720 KB Output is correct
23 Correct 1583 ms 92244 KB Output is correct
24 Correct 131 ms 38484 KB Output is correct
25 Correct 115 ms 37844 KB Output is correct
26 Correct 109 ms 37204 KB Output is correct
27 Correct 112 ms 37204 KB Output is correct
28 Correct 110 ms 37460 KB Output is correct
29 Correct 98 ms 36524 KB Output is correct
30 Correct 97 ms 36468 KB Output is correct
31 Correct 118 ms 37096 KB Output is correct
32 Correct 69 ms 35864 KB Output is correct
33 Correct 107 ms 37068 KB Output is correct
34 Correct 299 ms 46076 KB Output is correct
35 Correct 331 ms 46180 KB Output is correct
36 Correct 274 ms 44788 KB Output is correct
37 Correct 300 ms 44760 KB Output is correct
38 Correct 274 ms 44788 KB Output is correct
39 Correct 250 ms 42464 KB Output is correct
40 Correct 262 ms 42628 KB Output is correct
41 Correct 272 ms 43340 KB Output is correct
42 Correct 272 ms 43604 KB Output is correct
43 Correct 275 ms 43344 KB Output is correct
44 Correct 291 ms 44116 KB Output is correct
45 Correct 289 ms 44108 KB Output is correct
46 Correct 279 ms 43992 KB Output is correct
47 Correct 292 ms 43968 KB Output is correct
48 Correct 297 ms 44112 KB Output is correct
49 Correct 251 ms 42512 KB Output is correct
50 Correct 241 ms 42320 KB Output is correct
51 Correct 237 ms 42036 KB Output is correct
52 Correct 237 ms 42068 KB Output is correct
53 Correct 248 ms 42320 KB Output is correct
54 Correct 253 ms 43200 KB Output is correct
55 Correct 240 ms 41416 KB Output is correct
56 Correct 223 ms 42192 KB Output is correct
57 Correct 1780 ms 98056 KB Output is correct
58 Correct 1740 ms 98052 KB Output is correct
59 Correct 1642 ms 95148 KB Output is correct
60 Correct 1637 ms 95272 KB Output is correct
61 Correct 1644 ms 95188 KB Output is correct
62 Correct 1682 ms 95252 KB Output is correct
63 Correct 1282 ms 83348 KB Output is correct
64 Correct 1254 ms 83376 KB Output is correct
65 Correct 1586 ms 88592 KB Output is correct
66 Correct 1505 ms 88476 KB Output is correct
67 Correct 1497 ms 88656 KB Output is correct
68 Correct 1559 ms 91744 KB Output is correct
69 Correct 1583 ms 91568 KB Output is correct
70 Correct 1611 ms 91220 KB Output is correct
71 Correct 1593 ms 91288 KB Output is correct
72 Correct 1559 ms 91228 KB Output is correct
73 Correct 1191 ms 80244 KB Output is correct
74 Correct 1232 ms 81264 KB Output is correct
75 Correct 1234 ms 80464 KB Output is correct
76 Correct 1220 ms 80384 KB Output is correct
77 Correct 1199 ms 80288 KB Output is correct
78 Correct 1338 ms 85716 KB Output is correct
79 Correct 1031 ms 74732 KB Output is correct
80 Correct 1280 ms 81136 KB Output is correct