oj.uz

Submission #308794

# Submission time Handle Problem Language Result Execution time Memory
308794 2020-10-02T00:10:49 Z nikatamliani Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2049 ms 98160 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct query{
    int index, l, k;
};
vector < query > q[N];
int n, m, a[N], L[N];
stack < int > st;
int tree[4 * N];
bool ans[N];
void update(int l, int r, int x, int v, int p) {
    if(l > x || r < x) return;
    if(l == r) {
        tree[p] = max(tree[p], v);
    } else {
        int m = l + r >> 1;
        update(l, m, x, v, p << 1);
        update(m + 1, r, x, v, p << 1 | 1);
        tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
    }
}
int cnt(int l, int r, int L, int R, int p) {
    if(L > r || l > R) return 0;
    if(L <= l && R >= r) return tree[p];
    int m = l + r >> 1;
    return max(cnt(l, m, L, R, p << 1), cnt(m + 1, r, L, R, p << 1 | 1));
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) scanf("%d", a + i);
    for(int i = 1; i <= m; ++i) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        q[r].push_back({i, l, k});
    }
    for(int i = 1; i <= n; ++i) {
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        if(!st.empty()) {
            L[i] = st.top();
        }
        st.push(i);
    }
    for(int r = 1; r <= n; ++r) {
        if(L[r] > 0) {
            update(1, n, L[r], a[r] + a[L[r]], 1);
        }
        for(auto [index, l, k] : q[r]) {
            ans[index] = cnt(1, n, l, r, 1) <= k; 
        }
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
}

Compilation message

sortbooks.cpp: In function 'void update(int, int, int, int, int)':
sortbooks.cpp:17:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         int m = l + r >> 1;
      |                 ~~^~~
sortbooks.cpp: In function 'int cnt(int, int, int, int, int)':
sortbooks.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int m = l + r >> 1;
      |             ~~^~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:48:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for(auto [index, l, k] : q[r]) {
      |                  ^
sortbooks.cpp:31:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     for(int i = 1; i <= n; ++i) scanf("%d", a + i);
      |                                 ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%d%d%d", &l, &r, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 16 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 16 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 18 ms 23936 KB Output is correct
12 Correct 19 ms 24060 KB Output is correct
13 Correct 20 ms 24192 KB Output is correct
14 Correct 22 ms 24192 KB Output is correct
15 Correct 22 ms 24192 KB Output is correct
16 Correct 20 ms 24192 KB Output is correct
17 Correct 19 ms 24064 KB Output is correct
18 Correct 20 ms 24064 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2024 ms 64800 KB Output is correct
2 Correct 2049 ms 97556 KB Output is correct
3 Correct 2041 ms 97484 KB Output is correct
4 Correct 2016 ms 97788 KB Output is correct
5 Correct 1581 ms 85364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 28152 KB Output is correct
2 Correct 144 ms 29816 KB Output is correct
3 Correct 126 ms 28536 KB Output is correct
4 Correct 130 ms 28664 KB Output is correct
5 Correct 128 ms 28664 KB Output is correct
6 Correct 108 ms 28156 KB Output is correct
7 Correct 105 ms 28152 KB Output is correct
8 Correct 129 ms 28592 KB Output is correct
9 Correct 68 ms 26972 KB Output is correct
10 Correct 126 ms 28476 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 16 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 18 ms 23936 KB Output is correct
12 Correct 19 ms 24060 KB Output is correct
13 Correct 20 ms 24192 KB Output is correct
14 Correct 22 ms 24192 KB Output is correct
15 Correct 22 ms 24192 KB Output is correct
16 Correct 20 ms 24192 KB Output is correct
17 Correct 19 ms 24064 KB Output is correct
18 Correct 20 ms 24064 KB Output is correct
19 Correct 362 ms 39032 KB Output is correct
20 Correct 357 ms 39032 KB Output is correct
21 Correct 323 ms 38328 KB Output is correct
22 Correct 316 ms 38392 KB Output is correct
23 Correct 313 ms 38264 KB Output is correct
24 Correct 249 ms 35192 KB Output is correct
25 Correct 248 ms 35192 KB Output is correct
26 Correct 275 ms 35576 KB Output is correct
27 Correct 280 ms 35576 KB Output is correct
28 Correct 290 ms 35832 KB Output is correct
29 Correct 313 ms 36216 KB Output is correct
30 Correct 292 ms 36344 KB Output is correct
31 Correct 295 ms 36216 KB Output is correct
32 Correct 294 ms 36088 KB Output is correct
33 Correct 292 ms 36216 KB Output is correct
34 Correct 221 ms 34936 KB Output is correct
35 Correct 219 ms 34808 KB Output is correct
36 Correct 217 ms 34552 KB Output is correct
37 Correct 214 ms 34552 KB Output is correct
38 Correct 220 ms 34808 KB Output is correct
39 Correct 270 ms 35380 KB Output is correct
40 Correct 216 ms 33196 KB Output is correct
41 Correct 265 ms 34344 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 16 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 18 ms 23936 KB Output is correct
12 Correct 19 ms 24060 KB Output is correct
13 Correct 20 ms 24192 KB Output is correct
14 Correct 22 ms 24192 KB Output is correct
15 Correct 22 ms 24192 KB Output is correct
16 Correct 20 ms 24192 KB Output is correct
17 Correct 19 ms 24064 KB Output is correct
18 Correct 20 ms 24064 KB Output is correct
19 Correct 2024 ms 64800 KB Output is correct
20 Correct 2049 ms 97556 KB Output is correct
21 Correct 2041 ms 97484 KB Output is correct
22 Correct 2016 ms 97788 KB Output is correct
23 Correct 1581 ms 85364 KB Output is correct
24 Correct 156 ms 28152 KB Output is correct
25 Correct 144 ms 29816 KB Output is correct
26 Correct 126 ms 28536 KB Output is correct
27 Correct 130 ms 28664 KB Output is correct
28 Correct 128 ms 28664 KB Output is correct
29 Correct 108 ms 28156 KB Output is correct
30 Correct 105 ms 28152 KB Output is correct
31 Correct 129 ms 28592 KB Output is correct
32 Correct 68 ms 26972 KB Output is correct
33 Correct 126 ms 28476 KB Output is correct
34 Correct 362 ms 39032 KB Output is correct
35 Correct 357 ms 39032 KB Output is correct
36 Correct 323 ms 38328 KB Output is correct
37 Correct 316 ms 38392 KB Output is correct
38 Correct 313 ms 38264 KB Output is correct
39 Correct 249 ms 35192 KB Output is correct
40 Correct 248 ms 35192 KB Output is correct
41 Correct 275 ms 35576 KB Output is correct
42 Correct 280 ms 35576 KB Output is correct
43 Correct 290 ms 35832 KB Output is correct
44 Correct 313 ms 36216 KB Output is correct
45 Correct 292 ms 36344 KB Output is correct
46 Correct 295 ms 36216 KB Output is correct
47 Correct 294 ms 36088 KB Output is correct
48 Correct 292 ms 36216 KB Output is correct
49 Correct 221 ms 34936 KB Output is correct
50 Correct 219 ms 34808 KB Output is correct
51 Correct 217 ms 34552 KB Output is correct
52 Correct 214 ms 34552 KB Output is correct
53 Correct 220 ms 34808 KB Output is correct
54 Correct 270 ms 35380 KB Output is correct
55 Correct 216 ms 33196 KB Output is correct
56 Correct 265 ms 34344 KB Output is correct
57 Correct 2033 ms 97912 KB Output is correct
58 Correct 2041 ms 98160 KB Output is correct
59 Correct 1955 ms 96244 KB Output is correct
60 Correct 1949 ms 96332 KB Output is correct
61 Correct 1960 ms 96148 KB Output is correct
62 Correct 1987 ms 96500 KB Output is correct
63 Correct 1252 ms 80472 KB Output is correct
64 Correct 1257 ms 80284 KB Output is correct
65 Correct 1544 ms 83956 KB Output is correct
66 Correct 1585 ms 83956 KB Output is correct
67 Correct 1547 ms 84088 KB Output is correct
68 Correct 1598 ms 85624 KB Output is correct
69 Correct 1595 ms 85748 KB Output is correct
70 Correct 1586 ms 85368 KB Output is correct
71 Correct 1595 ms 85236 KB Output is correct
72 Correct 1628 ms 85364 KB Output is correct
73 Correct 1051 ms 76776 KB Output is correct
74 Correct 1055 ms 77556 KB Output is correct
75 Correct 1061 ms 76632 KB Output is correct
76 Correct 1071 ms 76660 KB Output is correct
77 Correct 1067 ms 76404 KB Output is correct
78 Correct 1445 ms 82080 KB Output is correct
79 Correct 1037 ms 69396 KB Output is correct
80 Correct 1450 ms 77968 KB Output is correct