oj.uz

Submission #711291

# Submission time Handle Problem Language Result Execution time Memory
711291 2023-03-16T13:57:30 Z onlk97 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1564 ms 141560 KB 
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
int seg[4000040];
void update(int id,int tl,int tr,int pos,int val){
    if (tl==tr){
        seg[id]=max(seg[id],val);
        return;
    }
    int tm=(tl+tr)/2;
    if (pos<=tm) update(2*id,tl,tm,pos,val);
    else update(2*id+1,tm+1,tr,pos,val);
    seg[id]=max(seg[2*id],seg[2*id+1]);
}
int query(int id,int tl,int tr,int l,int r){
    if (l>r) return 0;
    if (l<=tl&&tr<=r) return seg[id];
    int tm=(tl+tr)/2;
    int lx=query(2*id,tl,tm,l,min(r,tm));
    int rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return max(lx,rx);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin>>n>>m;
    int w[n+1];
    for (int i=1; i<=n; i++) cin>>w[i];
    tii qu[m+1];
    vector <tii> hang[n+1];
    for (int i=1; i<=m; i++){
        cin>>qu[i].x.x>>qu[i].x.y>>qu[i].y;
        hang[qu[i].x.y].pb({{qu[i].x.x,qu[i].y},i});
    }
    bool ans[m+1];
    for (int i=1; i<=m; i++) ans[i]=1;
    stack <pii> st;
    for (int i=1; i<=n; i++){
        while (!st.empty()&&st.top().x<=w[i]) st.pop();
        if (!st.empty()) update(1,1,n,st.top().y,w[st.top().y]+w[i]);
        st.push({w[i],i});
        for (auto j:hang[i]){
            if (query(1,1,n,j.x.x,i)>j.x.y) ans[j.y]=0;
        }
    }
    for (int i=1; i<=m; i++) cout<<ans[i]<<'\n';
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 852 KB Output is correct
14 Correct 5 ms 980 KB Output is correct
15 Correct 8 ms 980 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 4 ms 856 KB Output is correct
18 Correct 4 ms 852 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 107808 KB Output is correct
2 Correct 1406 ms 139860 KB Output is correct
3 Correct 1381 ms 139756 KB Output is correct
4 Correct 1414 ms 139900 KB Output is correct
5 Correct 1154 ms 123452 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 13388 KB Output is correct
2 Correct 115 ms 13532 KB Output is correct
3 Correct 81 ms 11328 KB Output is correct
4 Correct 84 ms 11408 KB Output is correct
5 Correct 76 ms 11344 KB Output is correct
6 Correct 71 ms 11224 KB Output is correct
7 Correct 68 ms 11280 KB Output is correct
8 Correct 67 ms 11096 KB Output is correct
9 Correct 40 ms 7180 KB Output is correct
10 Correct 74 ms 11056 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 852 KB Output is correct
14 Correct 5 ms 980 KB Output is correct
15 Correct 8 ms 980 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 4 ms 856 KB Output is correct
18 Correct 4 ms 852 KB Output is correct
19 Correct 224 ms 29040 KB Output is correct
20 Correct 243 ms 29016 KB Output is correct
21 Correct 207 ms 29424 KB Output is correct
22 Correct 183 ms 29520 KB Output is correct
23 Correct 197 ms 29512 KB Output is correct
24 Correct 191 ms 25292 KB Output is correct
25 Correct 149 ms 25420 KB Output is correct
26 Correct 225 ms 25308 KB Output is correct
27 Correct 165 ms 25164 KB Output is correct
28 Correct 202 ms 25080 KB Output is correct
29 Correct 193 ms 24988 KB Output is correct
30 Correct 193 ms 25000 KB Output is correct
31 Correct 238 ms 24984 KB Output is correct
32 Correct 193 ms 25036 KB Output is correct
33 Correct 189 ms 24992 KB Output is correct
34 Correct 180 ms 24648 KB Output is correct
35 Correct 154 ms 24732 KB Output is correct
36 Correct 168 ms 24572 KB Output is correct
37 Correct 185 ms 24580 KB Output is correct
38 Correct 161 ms 24772 KB Output is correct
39 Correct 235 ms 24400 KB Output is correct
40 Correct 123 ms 19764 KB Output is correct
41 Correct 176 ms 23244 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 852 KB Output is correct
14 Correct 5 ms 980 KB Output is correct
15 Correct 8 ms 980 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 4 ms 856 KB Output is correct
18 Correct 4 ms 852 KB Output is correct
19 Correct 1403 ms 107808 KB Output is correct
20 Correct 1406 ms 139860 KB Output is correct
21 Correct 1381 ms 139756 KB Output is correct
22 Correct 1414 ms 139900 KB Output is correct
23 Correct 1154 ms 123452 KB Output is correct
24 Correct 104 ms 13388 KB Output is correct
25 Correct 115 ms 13532 KB Output is correct
26 Correct 81 ms 11328 KB Output is correct
27 Correct 84 ms 11408 KB Output is correct
28 Correct 76 ms 11344 KB Output is correct
29 Correct 71 ms 11224 KB Output is correct
30 Correct 68 ms 11280 KB Output is correct
31 Correct 67 ms 11096 KB Output is correct
32 Correct 40 ms 7180 KB Output is correct
33 Correct 74 ms 11056 KB Output is correct
34 Correct 224 ms 29040 KB Output is correct
35 Correct 243 ms 29016 KB Output is correct
36 Correct 207 ms 29424 KB Output is correct
37 Correct 183 ms 29520 KB Output is correct
38 Correct 197 ms 29512 KB Output is correct
39 Correct 191 ms 25292 KB Output is correct
40 Correct 149 ms 25420 KB Output is correct
41 Correct 225 ms 25308 KB Output is correct
42 Correct 165 ms 25164 KB Output is correct
43 Correct 202 ms 25080 KB Output is correct
44 Correct 193 ms 24988 KB Output is correct
45 Correct 193 ms 25000 KB Output is correct
46 Correct 238 ms 24984 KB Output is correct
47 Correct 193 ms 25036 KB Output is correct
48 Correct 189 ms 24992 KB Output is correct
49 Correct 180 ms 24648 KB Output is correct
50 Correct 154 ms 24732 KB Output is correct
51 Correct 168 ms 24572 KB Output is correct
52 Correct 185 ms 24580 KB Output is correct
53 Correct 161 ms 24772 KB Output is correct
54 Correct 235 ms 24400 KB Output is correct
55 Correct 123 ms 19764 KB Output is correct
56 Correct 176 ms 23244 KB Output is correct
57 Correct 1431 ms 140880 KB Output is correct
58 Correct 1353 ms 140840 KB Output is correct
59 Correct 1284 ms 141468 KB Output is correct
60 Correct 1310 ms 141560 KB Output is correct
61 Correct 1312 ms 141336 KB Output is correct
62 Correct 1564 ms 141360 KB Output is correct
63 Correct 1073 ms 125152 KB Output is correct
64 Correct 946 ms 125144 KB Output is correct
65 Correct 1166 ms 125120 KB Output is correct
66 Correct 1137 ms 125252 KB Output is correct
67 Correct 1145 ms 125004 KB Output is correct
68 Correct 1162 ms 124296 KB Output is correct
69 Correct 1140 ms 124320 KB Output is correct
70 Correct 1204 ms 124052 KB Output is correct
71 Correct 1122 ms 123580 KB Output is correct
72 Correct 1122 ms 123536 KB Output is correct
73 Correct 826 ms 118688 KB Output is correct
74 Correct 848 ms 119584 KB Output is correct
75 Correct 827 ms 118460 KB Output is correct
76 Correct 777 ms 118996 KB Output is correct
77 Correct 781 ms 118480 KB Output is correct
78 Correct 1032 ms 120532 KB Output is correct
79 Correct 725 ms 93588 KB Output is correct
80 Correct 1047 ms 111536 KB Output is correct