oj.uz

Submission #501792

# Submission time Handle Problem Language Result Execution time Memory
501792 2022-01-04T14:54:09 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1351 ms 67012 KB 
#include <bits/stdc++.h>

using namespace std;

int t[4000005];

void update(int v, int tl, int tr, int pos, int val){
    if (tl == tr){
        t[v] = max(t[v], val);
        return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm) update(v + v, tl, tm, pos, val); else
        update(v + v + 1, tm + 1, tr, pos, val);

    t[v] = max(t[v + v], t[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r) return t[v];
    if (tl > r || tr < l) return 0;
    int tm = (tl + tr) >> 1;
    return max(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
}

int a[1000005];
vector<pair<int, pair<int, int>>> queries[1000005];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for (int i = 1; i <= q; i++){
        int l, r, k;
        cin >> l >> r >> k;
        queries[r].emplace_back(l, make_pair(k, i));
    }

    bitset<1000001> ans;

    a[0] = 2e9;
    stack<int> st;
    st.push(0);
    for (int i = 1; i <= n; i++){
        while (a[st.top()] <= a[i]) st.pop();
        int j = st.top();
        if (j != 0) update(1, 1, n, j, a[j] + a[i]);

        for (auto qu : queries[i]){
            int l = qu.first, k = qu.second.first, ind = qu.second.second;
            ans[ind] = get(1, 1, n, l, i) <= k;
        }

        st.push(i);
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';


    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 16 ms 23804 KB Output is correct
3 Correct 14 ms 23884 KB Output is correct
4 Correct 13 ms 23940 KB Output is correct
5 Correct 13 ms 23808 KB Output is correct
6 Correct 16 ms 23844 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 12 ms 23884 KB Output is correct
9 Correct 13 ms 23884 KB Output is correct
10 Correct 13 ms 23884 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 16 ms 23804 KB Output is correct
3 Correct 14 ms 23884 KB Output is correct
4 Correct 13 ms 23940 KB Output is correct
5 Correct 13 ms 23808 KB Output is correct
6 Correct 16 ms 23844 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 12 ms 23884 KB Output is correct
9 Correct 13 ms 23884 KB Output is correct
10 Correct 13 ms 23884 KB Output is correct
11 Correct 14 ms 23924 KB Output is correct
12 Correct 15 ms 24012 KB Output is correct
13 Correct 15 ms 24036 KB Output is correct
14 Correct 16 ms 24028 KB Output is correct
15 Correct 16 ms 24140 KB Output is correct
16 Correct 17 ms 24100 KB Output is correct
17 Correct 19 ms 24012 KB Output is correct
18 Correct 16 ms 24012 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 59704 KB Output is correct
2 Correct 1264 ms 66924 KB Output is correct
3 Correct 1303 ms 66996 KB Output is correct
4 Correct 1225 ms 67012 KB Output is correct
5 Correct 1115 ms 58828 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 27592 KB Output is correct
2 Correct 91 ms 27488 KB Output is correct
3 Correct 79 ms 26456 KB Output is correct
4 Correct 81 ms 26564 KB Output is correct
5 Correct 85 ms 26616 KB Output is correct
6 Correct 89 ms 26112 KB Output is correct
7 Correct 73 ms 26172 KB Output is correct
8 Correct 79 ms 26624 KB Output is correct
9 Correct 47 ms 25572 KB Output is correct
10 Correct 81 ms 26560 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 16 ms 23804 KB Output is correct
3 Correct 14 ms 23884 KB Output is correct
4 Correct 13 ms 23940 KB Output is correct
5 Correct 13 ms 23808 KB Output is correct
6 Correct 16 ms 23844 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 12 ms 23884 KB Output is correct
9 Correct 13 ms 23884 KB Output is correct
10 Correct 13 ms 23884 KB Output is correct
11 Correct 14 ms 23924 KB Output is correct
12 Correct 15 ms 24012 KB Output is correct
13 Correct 15 ms 24036 KB Output is correct
14 Correct 16 ms 24028 KB Output is correct
15 Correct 16 ms 24140 KB Output is correct
16 Correct 17 ms 24100 KB Output is correct
17 Correct 19 ms 24012 KB Output is correct
18 Correct 16 ms 24012 KB Output is correct
19 Correct 205 ms 31336 KB Output is correct
20 Correct 220 ms 31332 KB Output is correct
21 Correct 201 ms 30892 KB Output is correct
22 Correct 183 ms 30876 KB Output is correct
23 Correct 205 ms 30780 KB Output is correct
24 Correct 161 ms 28768 KB Output is correct
25 Correct 147 ms 28740 KB Output is correct
26 Correct 181 ms 28952 KB Output is correct
27 Correct 181 ms 28912 KB Output is correct
28 Correct 167 ms 29036 KB Output is correct
29 Correct 177 ms 29252 KB Output is correct
30 Correct 211 ms 29304 KB Output is correct
31 Correct 182 ms 29240 KB Output is correct
32 Correct 205 ms 29296 KB Output is correct
33 Correct 195 ms 29284 KB Output is correct
34 Correct 142 ms 28500 KB Output is correct
35 Correct 152 ms 28404 KB Output is correct
36 Correct 161 ms 28532 KB Output is correct
37 Correct 138 ms 28372 KB Output is correct
38 Correct 154 ms 28392 KB Output is correct
39 Correct 160 ms 29692 KB Output is correct
40 Correct 132 ms 28512 KB Output is correct
41 Correct 154 ms 29216 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 16 ms 23804 KB Output is correct
3 Correct 14 ms 23884 KB Output is correct
4 Correct 13 ms 23940 KB Output is correct
5 Correct 13 ms 23808 KB Output is correct
6 Correct 16 ms 23844 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 12 ms 23884 KB Output is correct
9 Correct 13 ms 23884 KB Output is correct
10 Correct 13 ms 23884 KB Output is correct
11 Correct 14 ms 23924 KB Output is correct
12 Correct 15 ms 24012 KB Output is correct
13 Correct 15 ms 24036 KB Output is correct
14 Correct 16 ms 24028 KB Output is correct
15 Correct 16 ms 24140 KB Output is correct
16 Correct 17 ms 24100 KB Output is correct
17 Correct 19 ms 24012 KB Output is correct
18 Correct 16 ms 24012 KB Output is correct
19 Correct 1229 ms 59704 KB Output is correct
20 Correct 1264 ms 66924 KB Output is correct
21 Correct 1303 ms 66996 KB Output is correct
22 Correct 1225 ms 67012 KB Output is correct
23 Correct 1115 ms 58828 KB Output is correct
24 Correct 95 ms 27592 KB Output is correct
25 Correct 91 ms 27488 KB Output is correct
26 Correct 79 ms 26456 KB Output is correct
27 Correct 81 ms 26564 KB Output is correct
28 Correct 85 ms 26616 KB Output is correct
29 Correct 89 ms 26112 KB Output is correct
30 Correct 73 ms 26172 KB Output is correct
31 Correct 79 ms 26624 KB Output is correct
32 Correct 47 ms 25572 KB Output is correct
33 Correct 81 ms 26560 KB Output is correct
34 Correct 205 ms 31336 KB Output is correct
35 Correct 220 ms 31332 KB Output is correct
36 Correct 201 ms 30892 KB Output is correct
37 Correct 183 ms 30876 KB Output is correct
38 Correct 205 ms 30780 KB Output is correct
39 Correct 161 ms 28768 KB Output is correct
40 Correct 147 ms 28740 KB Output is correct
41 Correct 181 ms 28952 KB Output is correct
42 Correct 181 ms 28912 KB Output is correct
43 Correct 167 ms 29036 KB Output is correct
44 Correct 177 ms 29252 KB Output is correct
45 Correct 211 ms 29304 KB Output is correct
46 Correct 182 ms 29240 KB Output is correct
47 Correct 205 ms 29296 KB Output is correct
48 Correct 195 ms 29284 KB Output is correct
49 Correct 142 ms 28500 KB Output is correct
50 Correct 152 ms 28404 KB Output is correct
51 Correct 161 ms 28532 KB Output is correct
52 Correct 138 ms 28372 KB Output is correct
53 Correct 154 ms 28392 KB Output is correct
54 Correct 160 ms 29692 KB Output is correct
55 Correct 132 ms 28512 KB Output is correct
56 Correct 154 ms 29216 KB Output is correct
57 Correct 1286 ms 63360 KB Output is correct
58 Correct 1289 ms 63528 KB Output is correct
59 Correct 1170 ms 61920 KB Output is correct
60 Correct 1197 ms 61888 KB Output is correct
61 Correct 1149 ms 61928 KB Output is correct
62 Correct 1351 ms 61804 KB Output is correct
63 Correct 834 ms 52372 KB Output is correct
64 Correct 825 ms 52264 KB Output is correct
65 Correct 1002 ms 53628 KB Output is correct
66 Correct 1006 ms 53828 KB Output is correct
67 Correct 956 ms 49856 KB Output is correct
68 Correct 1080 ms 55572 KB Output is correct
69 Correct 1089 ms 55480 KB Output is correct
70 Correct 1099 ms 55104 KB Output is correct
71 Correct 1061 ms 55088 KB Output is correct
72 Correct 1038 ms 55148 KB Output is correct
73 Correct 705 ms 50196 KB Output is correct
74 Correct 750 ms 50292 KB Output is correct
75 Correct 710 ms 50248 KB Output is correct
76 Correct 715 ms 50296 KB Output is correct
77 Correct 714 ms 50116 KB Output is correct
78 Correct 887 ms 56596 KB Output is correct
79 Correct 652 ms 49892 KB Output is correct
80 Correct 871 ms 53956 KB Output is correct