oj.uz

Submission #867823

# Submission time Handle Problem Language Result Execution time Memory
867823 2023-10-29T14:19:18 Z 12345678 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1528 ms 85432 KB 
#include <bits/stdc++.h>
#pragma gcc optimize("O3, unroll-loops")

using namespace std;

const int nx=1e6+5;
int n, m, v[nx], l, r, k, ans[nx];
vector<tuple<int, int, int>> d[nx];
stack<int> st;

struct segtree
{
    int d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i];
        if (l==r) return void(lz[i]=0);
        lz[2*i]+=lz[i];
        lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void setval(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=v[idx]);
        int md=(l+r)/2;
        setval(l, md, 2*i, idx);
        setval(md+1, r, 2*i+1, idx);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ul, int ur, int vl)
    {
        if (ur<ul) return;
        pushlz(l, r, i);
        if (r<ul||ur<l) return;
        if (ul<=l&&r<=ur) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ul, ur, vl);
        update(md+1, r, 2*i+1, ul, ur, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (r<ql||qr<l) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>v[i];
    for (int i=1; i<=4*n; i++) s.d[i]=INT_MIN;
    v[n+1]=INT_MAX;
    for (int i=0; i<m; i++) cin>>l>>r>>k, d[l].push_back({r, k, i});
    st.push(n+1);
    for (int i=n; i>=1; i--)
    {
        while (st.size()>1&&v[i]>v[st.top()])
        {
            int x=st.top();
            st.pop();
            s.setval(1, n, 1, x);
            s.update(1, n, 1, x+1, st.top()-1, -v[x]);
        }
        s.update(1, n, 1, i+1, st.top()-1, v[i]);
        st.push(i);
        for (auto [a, b, c]:d[i]) ans[c]=s.query(1, n, 1, i+1, a)<=b;
    }
    for (int i=0; i<m; i++) cout<<ans[i]<<'\n';
}

Compilation message

sortbooks.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3, unroll-loops")
      |

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 5 ms 26968 KB Output is correct
3 Correct 5 ms 26968 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 6 ms 26968 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 27076 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 6 ms 26972 KB Output is correct
11 Correct 9 ms 27228 KB Output is correct
12 Correct 9 ms 27140 KB Output is correct
13 Correct 9 ms 27340 KB Output is correct
14 Correct 12 ms 27228 KB Output is correct
15 Correct 10 ms 27224 KB Output is correct
16 Correct 8 ms 27224 KB Output is correct
17 Correct 8 ms 27228 KB Output is correct
18 Correct 8 ms 27228 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1472 ms 80660 KB Output is correct
2 Correct 1426 ms 80656 KB Output is correct
3 Correct 1442 ms 80404 KB Output is correct
4 Correct 1451 ms 80624 KB Output is correct
5 Correct 985 ms 84748 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 34644 KB Output is correct
2 Correct 96 ms 34384 KB Output is correct
3 Correct 76 ms 34776 KB Output is correct
4 Correct 78 ms 35028 KB Output is correct
5 Correct 69 ms 35152 KB Output is correct
6 Correct 60 ms 33620 KB Output is correct
7 Correct 57 ms 33620 KB Output is correct
8 Correct 71 ms 34440 KB Output is correct
9 Correct 37 ms 28692 KB Output is correct
10 Correct 86 ms 34480 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 5 ms 26968 KB Output is correct
3 Correct 5 ms 26968 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 6 ms 26968 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 27076 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 6 ms 26972 KB Output is correct
11 Correct 9 ms 27228 KB Output is correct
12 Correct 9 ms 27140 KB Output is correct
13 Correct 9 ms 27340 KB Output is correct
14 Correct 12 ms 27228 KB Output is correct
15 Correct 10 ms 27224 KB Output is correct
16 Correct 8 ms 27224 KB Output is correct
17 Correct 8 ms 27228 KB Output is correct
18 Correct 8 ms 27228 KB Output is correct
19 Correct 250 ms 41296 KB Output is correct
20 Correct 290 ms 41488 KB Output is correct
21 Correct 219 ms 40764 KB Output is correct
22 Correct 245 ms 40788 KB Output is correct
23 Correct 218 ms 40616 KB Output is correct
24 Correct 129 ms 40784 KB Output is correct
25 Correct 156 ms 40764 KB Output is correct
26 Correct 160 ms 41268 KB Output is correct
27 Correct 153 ms 41300 KB Output is correct
28 Correct 154 ms 41572 KB Output is correct
29 Correct 192 ms 42012 KB Output is correct
30 Correct 176 ms 42176 KB Output is correct
31 Correct 179 ms 41984 KB Output is correct
32 Correct 182 ms 41964 KB Output is correct
33 Correct 162 ms 42116 KB Output is correct
34 Correct 118 ms 39760 KB Output is correct
35 Correct 135 ms 39760 KB Output is correct
36 Correct 117 ms 39652 KB Output is correct
37 Correct 127 ms 39756 KB Output is correct
38 Correct 139 ms 39672 KB Output is correct
39 Correct 167 ms 40964 KB Output is correct
40 Correct 118 ms 38536 KB Output is correct
41 Correct 142 ms 40744 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 5 ms 26968 KB Output is correct
3 Correct 5 ms 26968 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 6 ms 26968 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 27076 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 6 ms 26972 KB Output is correct
11 Correct 9 ms 27228 KB Output is correct
12 Correct 9 ms 27140 KB Output is correct
13 Correct 9 ms 27340 KB Output is correct
14 Correct 12 ms 27228 KB Output is correct
15 Correct 10 ms 27224 KB Output is correct
16 Correct 8 ms 27224 KB Output is correct
17 Correct 8 ms 27228 KB Output is correct
18 Correct 8 ms 27228 KB Output is correct
19 Correct 1472 ms 80660 KB Output is correct
20 Correct 1426 ms 80656 KB Output is correct
21 Correct 1442 ms 80404 KB Output is correct
22 Correct 1451 ms 80624 KB Output is correct
23 Correct 985 ms 84748 KB Output is correct
24 Correct 107 ms 34644 KB Output is correct
25 Correct 96 ms 34384 KB Output is correct
26 Correct 76 ms 34776 KB Output is correct
27 Correct 78 ms 35028 KB Output is correct
28 Correct 69 ms 35152 KB Output is correct
29 Correct 60 ms 33620 KB Output is correct
30 Correct 57 ms 33620 KB Output is correct
31 Correct 71 ms 34440 KB Output is correct
32 Correct 37 ms 28692 KB Output is correct
33 Correct 86 ms 34480 KB Output is correct
34 Correct 250 ms 41296 KB Output is correct
35 Correct 290 ms 41488 KB Output is correct
36 Correct 219 ms 40764 KB Output is correct
37 Correct 245 ms 40788 KB Output is correct
38 Correct 218 ms 40616 KB Output is correct
39 Correct 129 ms 40784 KB Output is correct
40 Correct 156 ms 40764 KB Output is correct
41 Correct 160 ms 41268 KB Output is correct
42 Correct 153 ms 41300 KB Output is correct
43 Correct 154 ms 41572 KB Output is correct
44 Correct 192 ms 42012 KB Output is correct
45 Correct 176 ms 42176 KB Output is correct
46 Correct 179 ms 41984 KB Output is correct
47 Correct 182 ms 41964 KB Output is correct
48 Correct 162 ms 42116 KB Output is correct
49 Correct 118 ms 39760 KB Output is correct
50 Correct 135 ms 39760 KB Output is correct
51 Correct 117 ms 39652 KB Output is correct
52 Correct 127 ms 39756 KB Output is correct
53 Correct 139 ms 39672 KB Output is correct
54 Correct 167 ms 40964 KB Output is correct
55 Correct 118 ms 38536 KB Output is correct
56 Correct 142 ms 40744 KB Output is correct
57 Correct 1528 ms 81344 KB Output is correct
58 Correct 1528 ms 81172 KB Output is correct
59 Correct 1483 ms 79184 KB Output is correct
60 Correct 1273 ms 79608 KB Output is correct
61 Correct 1277 ms 79212 KB Output is correct
62 Correct 1303 ms 79164 KB Output is correct
63 Correct 662 ms 76628 KB Output is correct
64 Correct 619 ms 76752 KB Output is correct
65 Correct 883 ms 83336 KB Output is correct
66 Correct 920 ms 83280 KB Output is correct
67 Correct 875 ms 83536 KB Output is correct
68 Correct 1049 ms 85432 KB Output is correct
69 Correct 1145 ms 85284 KB Output is correct
70 Correct 1022 ms 85012 KB Output is correct
71 Correct 964 ms 85096 KB Output is correct
72 Correct 985 ms 85060 KB Output is correct
73 Correct 601 ms 76324 KB Output is correct
74 Correct 604 ms 76332 KB Output is correct
75 Correct 591 ms 76392 KB Output is correct
76 Correct 599 ms 76492 KB Output is correct
77 Correct 603 ms 76504 KB Output is correct
78 Correct 994 ms 80040 KB Output is correct
79 Correct 645 ms 65152 KB Output is correct
80 Correct 883 ms 80288 KB Output is correct