oj.uz

Submission #479293

# Submission time Handle Problem Language Result Execution time Memory
479293 2021-10-11T07:25:13 Z nafis_shifat Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1757 ms 142560 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e6+5;
const int inf = 2e9 + 10;
int n, m;
int a[mxn] = {};

struct segtree {
    int tree[4*mxn];
    void update(int node,int b,int e, int p, int v) {
        if(b > p || e < p) return;
        if(b == e) {
            tree[node] = v;
            return;
        }

        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;
        update(left, b, mid, p, v);
        update(right, mid + 1, e, p, v);
        tree[node] = max(tree[left], tree[right]);
    }
    int query(int node,int b,int e,int l,int r) {
        if(e<l || b>r) return 0;
        if(b >= l && e <= r) return tree[node];
        int mid=b+e>>1;
        int left=node<<1;
        int right=left|1;
        return max(query(left, b, mid, l, r), query(right, mid + 1, e, l, r));
    }
} st;


struct BIT
{
    int bit[mxn] = {}; 

    void update(int p,int v) {
        if(p==0) return;
        for(;p<mxn;p+=p&-p) bit[p] += v;
    }
    int query(int p) {
        int r = 0;
        for(;p > 0; p -= p&-p) r += bit[p];
        return r;
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} bt, dn;
int main() {
    cin >> n >> m;
    vector<pii> b;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);

        b.emplace_back(a[i], i);
    }

    a[0] = inf;

    stack<int> St;
    St.push(0);
    int nxt[n + 5];

    vector<int> con[n + 5];

    for(int i = 1; i <= n; i++) {
        while(a[St.top()] <= a[i]) St.pop();

        con[St.top()].push_back(i);

        if(St.top() != 0) st.update(1, 1, n, i, a[St.top()] + a[i]);

        St.push(i);
        
    }



    vector< tuple<int,int, int> > query[n + 1];

    for(int i = 1; i <= m; i++) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);

        query[l].emplace_back(r, i, k);
    }

    bool res[m + 1];

    for(int l = 1; l <= n; l++) {
        for(auto [r, i, k] : query[l]) {
            int v = st.query(1, 1, n, l, r);
            res[i] = (v <= k);
        }

        for(int x : con[l]) {
            st.update(1, 1, n, x, 0);
        }

    }

    for(int i = 1; i <= m; i++) {
        printf("%d\n", res[i]);
    }




}

Compilation message

sortbooks.cpp: In member function 'void segtree::update(int, int, int, int, int)':
sortbooks.cpp:19:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         int mid = b + e >> 1;
      |                   ~~^~~
sortbooks.cpp: In member function 'int segtree::query(int, int, int, int, int)':
sortbooks.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid=b+e>>1;
      |                 ~^~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:68:9: warning: unused variable 'nxt' [-Wunused-variable]
   68 |     int nxt[n + 5];
      |         ^~~
sortbooks.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d%d%d", &l, &r, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 8 ms 844 KB Output is correct
14 Correct 6 ms 972 KB Output is correct
15 Correct 7 ms 972 KB Output is correct
16 Correct 5 ms 844 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 4 ms 844 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1732 ms 108224 KB Output is correct
2 Correct 1731 ms 108168 KB Output is correct
3 Correct 1713 ms 108100 KB Output is correct
4 Correct 1706 ms 108148 KB Output is correct
5 Correct 1338 ms 87772 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 11320 KB Output is correct
2 Correct 112 ms 13088 KB Output is correct
3 Correct 91 ms 10920 KB Output is correct
4 Correct 97 ms 11060 KB Output is correct
5 Correct 95 ms 11092 KB Output is correct
6 Correct 75 ms 10524 KB Output is correct
7 Correct 72 ms 10552 KB Output is correct
8 Correct 98 ms 11428 KB Output is correct
9 Correct 41 ms 3432 KB Output is correct
10 Correct 102 ms 11320 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 8 ms 844 KB Output is correct
14 Correct 6 ms 972 KB Output is correct
15 Correct 7 ms 972 KB Output is correct
16 Correct 5 ms 844 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 4 ms 844 KB Output is correct
19 Correct 300 ms 29028 KB Output is correct
20 Correct 302 ms 29104 KB Output is correct
21 Correct 252 ms 28348 KB Output is correct
22 Correct 254 ms 28380 KB Output is correct
23 Correct 263 ms 28328 KB Output is correct
24 Correct 176 ms 23728 KB Output is correct
25 Correct 181 ms 23648 KB Output is correct
26 Correct 211 ms 24112 KB Output is correct
27 Correct 201 ms 23984 KB Output is correct
28 Correct 221 ms 24000 KB Output is correct
29 Correct 233 ms 24472 KB Output is correct
30 Correct 237 ms 24436 KB Output is correct
31 Correct 230 ms 24508 KB Output is correct
32 Correct 236 ms 24496 KB Output is correct
33 Correct 239 ms 24540 KB Output is correct
34 Correct 163 ms 22960 KB Output is correct
35 Correct 163 ms 23036 KB Output is correct
36 Correct 163 ms 22832 KB Output is correct
37 Correct 173 ms 22740 KB Output is correct
38 Correct 164 ms 22960 KB Output is correct
39 Correct 210 ms 23880 KB Output is correct
40 Correct 158 ms 17292 KB Output is correct
41 Correct 205 ms 23752 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 8 ms 844 KB Output is correct
14 Correct 6 ms 972 KB Output is correct
15 Correct 7 ms 972 KB Output is correct
16 Correct 5 ms 844 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 4 ms 844 KB Output is correct
19 Correct 1732 ms 108224 KB Output is correct
20 Correct 1731 ms 108168 KB Output is correct
21 Correct 1713 ms 108100 KB Output is correct
22 Correct 1706 ms 108148 KB Output is correct
23 Correct 1338 ms 87772 KB Output is correct
24 Correct 122 ms 11320 KB Output is correct
25 Correct 112 ms 13088 KB Output is correct
26 Correct 91 ms 10920 KB Output is correct
27 Correct 97 ms 11060 KB Output is correct
28 Correct 95 ms 11092 KB Output is correct
29 Correct 75 ms 10524 KB Output is correct
30 Correct 72 ms 10552 KB Output is correct
31 Correct 98 ms 11428 KB Output is correct
32 Correct 41 ms 3432 KB Output is correct
33 Correct 102 ms 11320 KB Output is correct
34 Correct 300 ms 29028 KB Output is correct
35 Correct 302 ms 29104 KB Output is correct
36 Correct 252 ms 28348 KB Output is correct
37 Correct 254 ms 28380 KB Output is correct
38 Correct 263 ms 28328 KB Output is correct
39 Correct 176 ms 23728 KB Output is correct
40 Correct 181 ms 23648 KB Output is correct
41 Correct 211 ms 24112 KB Output is correct
42 Correct 201 ms 23984 KB Output is correct
43 Correct 221 ms 24000 KB Output is correct
44 Correct 233 ms 24472 KB Output is correct
45 Correct 237 ms 24436 KB Output is correct
46 Correct 230 ms 24508 KB Output is correct
47 Correct 236 ms 24496 KB Output is correct
48 Correct 239 ms 24540 KB Output is correct
49 Correct 163 ms 22960 KB Output is correct
50 Correct 163 ms 23036 KB Output is correct
51 Correct 163 ms 22832 KB Output is correct
52 Correct 173 ms 22740 KB Output is correct
53 Correct 164 ms 22960 KB Output is correct
54 Correct 210 ms 23880 KB Output is correct
55 Correct 158 ms 17292 KB Output is correct
56 Correct 205 ms 23752 KB Output is correct
57 Correct 1711 ms 142560 KB Output is correct
58 Correct 1757 ms 142492 KB Output is correct
59 Correct 1701 ms 140460 KB Output is correct
60 Correct 1705 ms 140336 KB Output is correct
61 Correct 1705 ms 140304 KB Output is correct
62 Correct 1733 ms 140320 KB Output is correct
63 Correct 983 ms 114324 KB Output is correct
64 Correct 906 ms 114472 KB Output is correct
65 Correct 1285 ms 119920 KB Output is correct
66 Correct 1288 ms 119948 KB Output is correct
67 Correct 1292 ms 119860 KB Output is correct
68 Correct 1389 ms 122096 KB Output is correct
69 Correct 1419 ms 122016 KB Output is correct
70 Correct 1402 ms 121608 KB Output is correct
71 Correct 1409 ms 121608 KB Output is correct
72 Correct 1427 ms 121468 KB Output is correct
73 Correct 890 ms 111964 KB Output is correct
74 Correct 855 ms 112680 KB Output is correct
75 Correct 870 ms 111876 KB Output is correct
76 Correct 1070 ms 111780 KB Output is correct
77 Correct 960 ms 112024 KB Output is correct
78 Correct 1429 ms 118704 KB Output is correct
79 Correct 1010 ms 76360 KB Output is correct
80 Correct 1321 ms 115296 KB Output is correct