oj.uz

Submission #436109

# Submission time Handle Problem Language Result Execution time Memory
436109 2021-06-24T08:57:34 Z cpp219 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1365 ms 92336 KB 
#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 9;
const ll inf = 1e9 + 7;

struct Query{
    ll l,k,id;
};
vector<Query> v[N];
stack<ll> st;
ll n,Q,ans[N],a[N],l,r,k,bit[N];

void upd(ll p,ll val){
    for (ll i = p;i > 0;i -= i & -i) bit[i] = max(bit[i],val);
}

ll Get(ll p){
    ll res = 0;
    for (ll i = p;i <= n;i += i & -i) res = max(res,bit[i]);
    return res;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++) cin>>a[i]; a[0] = inf;
    for (ll i = 1;i <= Q;i++){
        cin>>l>>r>>k;
        v[r].push_back({l,k,i});
    }
    st.push(0);
    for (ll i = 1;i <= n;i++){
        while(a[st.top()] <= a[i]) st.pop();
        if (st.top()) upd(st.top(),a[st.top()] + a[i]); st.push(i);
        for (auto j : v[i]){
            ll id = j.id;
            ans[id] = (Get(j.l) <= j.k);
        }
    }
    for (ll i = 1;i <= Q;i++) cout<<ans[i]<<"\n";
}

Compilation message

sortbooks.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
sortbooks.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
sortbooks.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:40:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |     for (ll i = 1;i <= n;i++) cin>>a[i]; a[0] = inf;
      |     ^~~
sortbooks.cpp:40:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |     for (ll i = 1;i <= n;i++) cin>>a[i]; a[0] = inf;
      |                                          ^
sortbooks.cpp:48:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |         if (st.top()) upd(st.top(),a[st.top()] + a[i]); st.push(i);
      |         ^~
sortbooks.cpp:48:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |         if (st.top()) upd(st.top(),a[st.top()] + a[i]); st.push(i);
      |                                                         ^~
sortbooks.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 19 ms 23752 KB Output is correct
3 Correct 18 ms 23832 KB Output is correct
4 Correct 22 ms 23780 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 21 ms 23756 KB Output is correct
7 Correct 20 ms 23816 KB Output is correct
8 Correct 17 ms 23812 KB Output is correct
9 Correct 17 ms 23756 KB Output is correct
10 Correct 17 ms 23756 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 19 ms 23752 KB Output is correct
3 Correct 18 ms 23832 KB Output is correct
4 Correct 22 ms 23780 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 21 ms 23756 KB Output is correct
7 Correct 20 ms 23816 KB Output is correct
8 Correct 17 ms 23812 KB Output is correct
9 Correct 17 ms 23756 KB Output is correct
10 Correct 17 ms 23756 KB Output is correct
11 Correct 19 ms 23948 KB Output is correct
12 Correct 23 ms 23936 KB Output is correct
13 Correct 21 ms 24012 KB Output is correct
14 Correct 22 ms 24140 KB Output is correct
15 Correct 21 ms 24152 KB Output is correct
16 Correct 22 ms 24068 KB Output is correct
17 Correct 20 ms 24068 KB Output is correct
18 Correct 22 ms 24080 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 91140 KB Output is correct
2 Correct 1196 ms 91996 KB Output is correct
3 Correct 1365 ms 91988 KB Output is correct
4 Correct 1298 ms 92044 KB Output is correct
5 Correct 1188 ms 88124 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 29272 KB Output is correct
2 Correct 93 ms 28972 KB Output is correct
3 Correct 83 ms 28808 KB Output is correct
4 Correct 82 ms 28800 KB Output is correct
5 Correct 86 ms 28864 KB Output is correct
6 Correct 82 ms 28336 KB Output is correct
7 Correct 77 ms 28272 KB Output is correct
8 Correct 78 ms 28456 KB Output is correct
9 Correct 59 ms 27212 KB Output is correct
10 Correct 86 ms 28412 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 19 ms 23752 KB Output is correct
3 Correct 18 ms 23832 KB Output is correct
4 Correct 22 ms 23780 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 21 ms 23756 KB Output is correct
7 Correct 20 ms 23816 KB Output is correct
8 Correct 17 ms 23812 KB Output is correct
9 Correct 17 ms 23756 KB Output is correct
10 Correct 17 ms 23756 KB Output is correct
11 Correct 19 ms 23948 KB Output is correct
12 Correct 23 ms 23936 KB Output is correct
13 Correct 21 ms 24012 KB Output is correct
14 Correct 22 ms 24140 KB Output is correct
15 Correct 21 ms 24152 KB Output is correct
16 Correct 22 ms 24068 KB Output is correct
17 Correct 20 ms 24068 KB Output is correct
18 Correct 22 ms 24080 KB Output is correct
19 Correct 208 ms 37480 KB Output is correct
20 Correct 197 ms 37392 KB Output is correct
21 Correct 179 ms 36676 KB Output is correct
22 Correct 175 ms 36660 KB Output is correct
23 Correct 166 ms 36712 KB Output is correct
24 Correct 160 ms 35780 KB Output is correct
25 Correct 177 ms 35908 KB Output is correct
26 Correct 170 ms 36068 KB Output is correct
27 Correct 179 ms 36044 KB Output is correct
28 Correct 189 ms 36184 KB Output is correct
29 Correct 185 ms 36612 KB Output is correct
30 Correct 217 ms 36588 KB Output is correct
31 Correct 194 ms 36500 KB Output is correct
32 Correct 221 ms 36548 KB Output is correct
33 Correct 185 ms 36560 KB Output is correct
34 Correct 155 ms 35396 KB Output is correct
35 Correct 150 ms 35356 KB Output is correct
36 Correct 169 ms 35056 KB Output is correct
37 Correct 171 ms 35168 KB Output is correct
38 Correct 177 ms 35236 KB Output is correct
39 Correct 172 ms 35036 KB Output is correct
40 Correct 158 ms 33448 KB Output is correct
41 Correct 194 ms 34408 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 19 ms 23752 KB Output is correct
3 Correct 18 ms 23832 KB Output is correct
4 Correct 22 ms 23780 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 21 ms 23756 KB Output is correct
7 Correct 20 ms 23816 KB Output is correct
8 Correct 17 ms 23812 KB Output is correct
9 Correct 17 ms 23756 KB Output is correct
10 Correct 17 ms 23756 KB Output is correct
11 Correct 19 ms 23948 KB Output is correct
12 Correct 23 ms 23936 KB Output is correct
13 Correct 21 ms 24012 KB Output is correct
14 Correct 22 ms 24140 KB Output is correct
15 Correct 21 ms 24152 KB Output is correct
16 Correct 22 ms 24068 KB Output is correct
17 Correct 20 ms 24068 KB Output is correct
18 Correct 22 ms 24080 KB Output is correct
19 Correct 1286 ms 91140 KB Output is correct
20 Correct 1196 ms 91996 KB Output is correct
21 Correct 1365 ms 91988 KB Output is correct
22 Correct 1298 ms 92044 KB Output is correct
23 Correct 1188 ms 88124 KB Output is correct
24 Correct 121 ms 29272 KB Output is correct
25 Correct 93 ms 28972 KB Output is correct
26 Correct 83 ms 28808 KB Output is correct
27 Correct 82 ms 28800 KB Output is correct
28 Correct 86 ms 28864 KB Output is correct
29 Correct 82 ms 28336 KB Output is correct
30 Correct 77 ms 28272 KB Output is correct
31 Correct 78 ms 28456 KB Output is correct
32 Correct 59 ms 27212 KB Output is correct
33 Correct 86 ms 28412 KB Output is correct
34 Correct 208 ms 37480 KB Output is correct
35 Correct 197 ms 37392 KB Output is correct
36 Correct 179 ms 36676 KB Output is correct
37 Correct 175 ms 36660 KB Output is correct
38 Correct 166 ms 36712 KB Output is correct
39 Correct 160 ms 35780 KB Output is correct
40 Correct 177 ms 35908 KB Output is correct
41 Correct 170 ms 36068 KB Output is correct
42 Correct 179 ms 36044 KB Output is correct
43 Correct 189 ms 36184 KB Output is correct
44 Correct 185 ms 36612 KB Output is correct
45 Correct 217 ms 36588 KB Output is correct
46 Correct 194 ms 36500 KB Output is correct
47 Correct 221 ms 36548 KB Output is correct
48 Correct 185 ms 36560 KB Output is correct
49 Correct 155 ms 35396 KB Output is correct
50 Correct 150 ms 35356 KB Output is correct
51 Correct 169 ms 35056 KB Output is correct
52 Correct 171 ms 35168 KB Output is correct
53 Correct 177 ms 35236 KB Output is correct
54 Correct 172 ms 35036 KB Output is correct
55 Correct 158 ms 33448 KB Output is correct
56 Correct 194 ms 34408 KB Output is correct
57 Correct 1220 ms 92188 KB Output is correct
58 Correct 1169 ms 92336 KB Output is correct
59 Correct 1062 ms 90736 KB Output is correct
60 Correct 1137 ms 90668 KB Output is correct
61 Correct 1203 ms 90820 KB Output is correct
62 Correct 1218 ms 90708 KB Output is correct
63 Correct 800 ms 83652 KB Output is correct
64 Correct 819 ms 83580 KB Output is correct
65 Correct 1056 ms 86636 KB Output is correct
66 Correct 1104 ms 86644 KB Output is correct
67 Correct 1089 ms 86672 KB Output is correct
68 Correct 1215 ms 88408 KB Output is correct
69 Correct 1130 ms 88268 KB Output is correct
70 Correct 1122 ms 87984 KB Output is correct
71 Correct 1105 ms 88080 KB Output is correct
72 Correct 1123 ms 88072 KB Output is correct
73 Correct 698 ms 79556 KB Output is correct
74 Correct 764 ms 80408 KB Output is correct
75 Correct 684 ms 79464 KB Output is correct
76 Correct 674 ms 79496 KB Output is correct
77 Correct 660 ms 79476 KB Output is correct
78 Correct 982 ms 81724 KB Output is correct
79 Correct 745 ms 71548 KB Output is correct
80 Correct 1031 ms 77596 KB Output is correct