oj.uz

Submission #169910

# Submission time Handle Problem Language Result Execution time Memory
169910 2019-12-23T08:56:34 Z juggernaut Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2355 ms 142112 KB 
//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n,m,pos[1000001],a[1000001],i,tree[4000001],l[1000001],r[1000001],k[1000001],ans[1000001];
vector<vector<int>>g(1000001);
void update(int v,int l,int r,int ind,int val){
    if(l==r){tree[v]=val;return;}
    int m=(l+r)>>1;
    if(ind<=m)update(v*2,l,m,ind,val);
    else update(v*2+1,m+1,r,ind,val);
    tree[v]=max(tree[v*2],tree[v*2+1]);
}
int get(int v,int l,int r,int ql,int qr){
    if(qr<l||r<ql)return 0;
    if(ql<=l&&r<=qr)return tree[v];
    int mid=(l+r)>>1;
    return max(get(v*2,l,mid,ql,qr),get(v*2+1,mid+1,r,ql,qr));
}
main(){
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        pos[i]=i-1;
        while(pos[i]&&a[pos[i]]<=a[i])pos[i]=pos[pos[i]];
    }
    for(i=1;i<=m;i++){
        scanf("%lld%lld%lld",&l[i],&r[i],&k[i]);
        g[r[i]].push_back(i);
    }
    for(i=1;i<=n;i++){
        if(pos[i])update(1,1,n,pos[i],a[i]+a[pos[i]]);
        for(int to:g[i])ans[to]=(get(1,1,n,l[to],r[to])<=k[to]?1:0);
    }
    for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
}

Compilation message

sortbooks.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
         ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&l[i],&r[i],&k[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Correct 24 ms 23932 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 24 ms 23900 KB Output is correct
6 Correct 25 ms 23900 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 29 ms 23928 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Correct 24 ms 23932 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 24 ms 23900 KB Output is correct
6 Correct 25 ms 23900 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 29 ms 23928 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Correct 27 ms 24184 KB Output is correct
12 Correct 28 ms 24312 KB Output is correct
13 Correct 28 ms 24312 KB Output is correct
14 Correct 30 ms 24576 KB Output is correct
15 Correct 30 ms 24544 KB Output is correct
16 Correct 32 ms 24312 KB Output is correct
17 Correct 28 ms 24312 KB Output is correct
18 Correct 28 ms 24312 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2242 ms 116316 KB Output is correct
2 Correct 2188 ms 142112 KB Output is correct
3 Correct 2218 ms 141800 KB Output is correct
4 Correct 2347 ms 141936 KB Output is correct
5 Correct 1770 ms 125648 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 34768 KB Output is correct
2 Correct 154 ms 34192 KB Output is correct
3 Correct 146 ms 32508 KB Output is correct
4 Correct 144 ms 32540 KB Output is correct
5 Correct 150 ms 32632 KB Output is correct
6 Correct 122 ms 31736 KB Output is correct
7 Correct 122 ms 31736 KB Output is correct
8 Correct 139 ms 32240 KB Output is correct
9 Correct 79 ms 29552 KB Output is correct
10 Correct 146 ms 32284 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Correct 24 ms 23932 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 24 ms 23900 KB Output is correct
6 Correct 25 ms 23900 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 29 ms 23928 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Correct 27 ms 24184 KB Output is correct
12 Correct 28 ms 24312 KB Output is correct
13 Correct 28 ms 24312 KB Output is correct
14 Correct 30 ms 24576 KB Output is correct
15 Correct 30 ms 24544 KB Output is correct
16 Correct 32 ms 24312 KB Output is correct
17 Correct 28 ms 24312 KB Output is correct
18 Correct 28 ms 24312 KB Output is correct
19 Correct 391 ms 48108 KB Output is correct
20 Correct 394 ms 48156 KB Output is correct
21 Correct 336 ms 46832 KB Output is correct
22 Correct 335 ms 46796 KB Output is correct
23 Correct 331 ms 46840 KB Output is correct
24 Correct 276 ms 42536 KB Output is correct
25 Correct 278 ms 42628 KB Output is correct
26 Correct 311 ms 43128 KB Output is correct
27 Correct 336 ms 43512 KB Output is correct
28 Correct 309 ms 43384 KB Output is correct
29 Correct 343 ms 44000 KB Output is correct
30 Correct 330 ms 44024 KB Output is correct
31 Correct 347 ms 44084 KB Output is correct
32 Correct 330 ms 44152 KB Output is correct
33 Correct 328 ms 43896 KB Output is correct
34 Correct 255 ms 42104 KB Output is correct
35 Correct 286 ms 42104 KB Output is correct
36 Correct 260 ms 42100 KB Output is correct
37 Correct 270 ms 41948 KB Output is correct
38 Correct 269 ms 42256 KB Output is correct
39 Correct 296 ms 43788 KB Output is correct
40 Correct 220 ms 40172 KB Output is correct
41 Correct 283 ms 42040 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Correct 24 ms 23932 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 24 ms 23900 KB Output is correct
6 Correct 25 ms 23900 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 29 ms 23928 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Correct 27 ms 24184 KB Output is correct
12 Correct 28 ms 24312 KB Output is correct
13 Correct 28 ms 24312 KB Output is correct
14 Correct 30 ms 24576 KB Output is correct
15 Correct 30 ms 24544 KB Output is correct
16 Correct 32 ms 24312 KB Output is correct
17 Correct 28 ms 24312 KB Output is correct
18 Correct 28 ms 24312 KB Output is correct
19 Correct 2242 ms 116316 KB Output is correct
20 Correct 2188 ms 142112 KB Output is correct
21 Correct 2218 ms 141800 KB Output is correct
22 Correct 2347 ms 141936 KB Output is correct
23 Correct 1770 ms 125648 KB Output is correct
24 Correct 181 ms 34768 KB Output is correct
25 Correct 154 ms 34192 KB Output is correct
26 Correct 146 ms 32508 KB Output is correct
27 Correct 144 ms 32540 KB Output is correct
28 Correct 150 ms 32632 KB Output is correct
29 Correct 122 ms 31736 KB Output is correct
30 Correct 122 ms 31736 KB Output is correct
31 Correct 139 ms 32240 KB Output is correct
32 Correct 79 ms 29552 KB Output is correct
33 Correct 146 ms 32284 KB Output is correct
34 Correct 391 ms 48108 KB Output is correct
35 Correct 394 ms 48156 KB Output is correct
36 Correct 336 ms 46832 KB Output is correct
37 Correct 335 ms 46796 KB Output is correct
38 Correct 331 ms 46840 KB Output is correct
39 Correct 276 ms 42536 KB Output is correct
40 Correct 278 ms 42628 KB Output is correct
41 Correct 311 ms 43128 KB Output is correct
42 Correct 336 ms 43512 KB Output is correct
43 Correct 309 ms 43384 KB Output is correct
44 Correct 343 ms 44000 KB Output is correct
45 Correct 330 ms 44024 KB Output is correct
46 Correct 347 ms 44084 KB Output is correct
47 Correct 330 ms 44152 KB Output is correct
48 Correct 328 ms 43896 KB Output is correct
49 Correct 255 ms 42104 KB Output is correct
50 Correct 286 ms 42104 KB Output is correct
51 Correct 260 ms 42100 KB Output is correct
52 Correct 270 ms 41948 KB Output is correct
53 Correct 269 ms 42256 KB Output is correct
54 Correct 296 ms 43788 KB Output is correct
55 Correct 220 ms 40172 KB Output is correct
56 Correct 283 ms 42040 KB Output is correct
57 Correct 2196 ms 141500 KB Output is correct
58 Correct 2314 ms 137564 KB Output is correct
59 Correct 2355 ms 133372 KB Output is correct
60 Correct 2178 ms 138768 KB Output is correct
61 Correct 2133 ms 136368 KB Output is correct
62 Correct 2132 ms 138716 KB Output is correct
63 Correct 1399 ms 116352 KB Output is correct
64 Correct 1419 ms 114292 KB Output is correct
65 Correct 1740 ms 122152 KB Output is correct
66 Correct 1718 ms 118992 KB Output is correct
67 Correct 1726 ms 117792 KB Output is correct
68 Correct 1771 ms 125244 KB Output is correct
69 Correct 1795 ms 125000 KB Output is correct
70 Correct 1760 ms 124576 KB Output is correct
71 Correct 1822 ms 120888 KB Output is correct
72 Correct 1821 ms 124688 KB Output is correct
73 Correct 1302 ms 113364 KB Output is correct
74 Correct 1303 ms 114664 KB Output is correct
75 Correct 1295 ms 113100 KB Output is correct
76 Correct 1300 ms 113988 KB Output is correct
77 Correct 1288 ms 113436 KB Output is correct
78 Correct 1584 ms 122400 KB Output is correct
79 Correct 1133 ms 102624 KB Output is correct
80 Correct 1589 ms 114824 KB Output is correct