oj.uz

Submission #336057

# Submission time Handle Problem Language Result Execution time Memory
336057 2020-12-14T15:21:46 Z beksultan04 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1707 ms 100996 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%lld",&a);
#define scan2(a,b) scanf("%lld %lld",&a, &b);
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
const int N = 1e6+12,INF=1e9+7;
int q[N],ct[N],der[4*N];

void update(int v,int l,int r,int x,int y){
    if (l == x && r == x){
        der[v] = y;
    }
    else {
        int m = l+r>>1;
        if (m<x)
            update((v<<1)+1,m+1,r,x,y);
        else
            update(v<<1,l,m,x,y);
        der[v]=max(der[v<<1],der[(v<<1)+1]);
    }
}

int get_ans(int v,int l,int r,int ql,int qr){
    if (qr < l || ql > r)ret 0;
    if (ql <= l && r<= qr)ret der[v];
    int m = l+r>>1;
    ret max(get_ans(v<<1,l,m,ql,qr),get_ans((v<<1)+1,m+1,r,ql,qr));
}

main(){
    deque <pair<pii,pii> > v;
    int n,t,i,j,cnt=1,res=0;
    scan2(n,t)
    for (i=1;i<=n;++i){
        scan1(q[i])
    }
    while (t--){
        int l,r,k;
        scan3(l,r,k)
        v.pb({{r,l},{k,cnt++}});
    }
    sort(all(v));
    vector <pii> ans;
    for (i=1;i<=n;++i){
        while (!ans.empty() && ans.back().fr < q[i]){
            ans.pop_back();
        }
        bool f=0;
        if (ans.empty()){
            ans.pb({q[i],i});
            f=1;
        }
        int x = ans.back().fr;
        int y = ans.back().sc;
        if (!f)
            ans.pb({q[i],i});
        if (x > q[i]){
            update(1,1,n,y,x+q[i]);
        }
        while (!v.empty() && v[0].fr.fr == i){
            res = get_ans(1,1,n,v[0].fr.sc,i);
            ct[v[0].sc.sc] = (v[0].sc.fr >=res);
            v.pop_front();
        }
    }
    for (i=1;i<cnt;++i)
        cout <<ct[i]<<"\n";
}

Compilation message

sortbooks.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:24:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         int m = l+r>>1;
      |                 ~^~
sortbooks.cpp: In function 'long long int get_ans(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int m = l+r>>1;
      |             ~^~
sortbooks.cpp: At global scope:
sortbooks.cpp:40:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      |      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:42:15: warning: unused variable 'j' [-Wunused-variable]
   42 |     int n,t,i,j,cnt=1,res=0;
      |               ^
sortbooks.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 | #define scan2(a,b) scanf("%lld %lld",&a, &b);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:43:5: note: in expansion of macro 'scan2'
   43 |     scan2(n,t)
      |     ^~~~~
sortbooks.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | #define scan1(a) scanf("%lld",&a);
      |                  ~~~~~^~~~~~~~~~~
sortbooks.cpp:45:9: note: in expansion of macro 'scan1'
   45 |         scan1(q[i])
      |         ^~~~~
sortbooks.cpp:11:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 | #define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:49:9: note: in expansion of macro 'scan3'
   49 |         scan3(l,r,k)
      |         ^~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 6 ms 620 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 6 ms 748 KB Output is correct
15 Correct 6 ms 748 KB Output is correct
16 Correct 5 ms 620 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 4 ms 748 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1707 ms 67436 KB Output is correct
2 Correct 1689 ms 67396 KB Output is correct
3 Correct 1685 ms 67428 KB Output is correct
4 Correct 1669 ms 67312 KB Output is correct
5 Correct 1330 ms 51184 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 7404 KB Output is correct
2 Correct 123 ms 9324 KB Output is correct
3 Correct 105 ms 7404 KB Output is correct
4 Correct 102 ms 7404 KB Output is correct
5 Correct 105 ms 7404 KB Output is correct
6 Correct 96 ms 7276 KB Output is correct
7 Correct 96 ms 7276 KB Output is correct
8 Correct 94 ms 8084 KB Output is correct
9 Correct 60 ms 5868 KB Output is correct
10 Correct 91 ms 8044 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 6 ms 620 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 6 ms 748 KB Output is correct
15 Correct 6 ms 748 KB Output is correct
16 Correct 5 ms 620 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 289 ms 19932 KB Output is correct
20 Correct 294 ms 20460 KB Output is correct
21 Correct 273 ms 20460 KB Output is correct
22 Correct 277 ms 20460 KB Output is correct
23 Correct 272 ms 20460 KB Output is correct
24 Correct 231 ms 16364 KB Output is correct
25 Correct 229 ms 16492 KB Output is correct
26 Correct 249 ms 16268 KB Output is correct
27 Correct 239 ms 16364 KB Output is correct
28 Correct 237 ms 16364 KB Output is correct
29 Correct 240 ms 16364 KB Output is correct
30 Correct 238 ms 16364 KB Output is correct
31 Correct 239 ms 16364 KB Output is correct
32 Correct 242 ms 16364 KB Output is correct
33 Correct 240 ms 16492 KB Output is correct
34 Correct 225 ms 16492 KB Output is correct
35 Correct 220 ms 16364 KB Output is correct
36 Correct 219 ms 16364 KB Output is correct
37 Correct 220 ms 16364 KB Output is correct
38 Correct 222 ms 16320 KB Output is correct
39 Correct 231 ms 17260 KB Output is correct
40 Correct 175 ms 14444 KB Output is correct
41 Correct 206 ms 17000 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 6 ms 620 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 6 ms 748 KB Output is correct
15 Correct 6 ms 748 KB Output is correct
16 Correct 5 ms 620 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 1707 ms 67436 KB Output is correct
20 Correct 1689 ms 67396 KB Output is correct
21 Correct 1685 ms 67428 KB Output is correct
22 Correct 1669 ms 67312 KB Output is correct
23 Correct 1330 ms 51184 KB Output is correct
24 Correct 123 ms 7404 KB Output is correct
25 Correct 123 ms 9324 KB Output is correct
26 Correct 105 ms 7404 KB Output is correct
27 Correct 102 ms 7404 KB Output is correct
28 Correct 105 ms 7404 KB Output is correct
29 Correct 96 ms 7276 KB Output is correct
30 Correct 96 ms 7276 KB Output is correct
31 Correct 94 ms 8084 KB Output is correct
32 Correct 60 ms 5868 KB Output is correct
33 Correct 91 ms 8044 KB Output is correct
34 Correct 289 ms 19932 KB Output is correct
35 Correct 294 ms 20460 KB Output is correct
36 Correct 273 ms 20460 KB Output is correct
37 Correct 277 ms 20460 KB Output is correct
38 Correct 272 ms 20460 KB Output is correct
39 Correct 231 ms 16364 KB Output is correct
40 Correct 229 ms 16492 KB Output is correct
41 Correct 249 ms 16268 KB Output is correct
42 Correct 239 ms 16364 KB Output is correct
43 Correct 237 ms 16364 KB Output is correct
44 Correct 240 ms 16364 KB Output is correct
45 Correct 238 ms 16364 KB Output is correct
46 Correct 239 ms 16364 KB Output is correct
47 Correct 242 ms 16364 KB Output is correct
48 Correct 240 ms 16492 KB Output is correct
49 Correct 225 ms 16492 KB Output is correct
50 Correct 220 ms 16364 KB Output is correct
51 Correct 219 ms 16364 KB Output is correct
52 Correct 220 ms 16364 KB Output is correct
53 Correct 222 ms 16320 KB Output is correct
54 Correct 231 ms 17260 KB Output is correct
55 Correct 175 ms 14444 KB Output is correct
56 Correct 206 ms 17000 KB Output is correct
57 Correct 1693 ms 100996 KB Output is correct
58 Correct 1690 ms 100976 KB Output is correct
59 Correct 1665 ms 100796 KB Output is correct
60 Correct 1652 ms 100976 KB Output is correct
61 Correct 1662 ms 100960 KB Output is correct
62 Correct 1647 ms 100848 KB Output is correct
63 Correct 1281 ms 82668 KB Output is correct
64 Correct 1258 ms 82576 KB Output is correct
65 Correct 1347 ms 84464 KB Output is correct
66 Correct 1353 ms 84356 KB Output is correct
67 Correct 1342 ms 84596 KB Output is correct
68 Correct 1341 ms 84648 KB Output is correct
69 Correct 1329 ms 84592 KB Output is correct
70 Correct 1344 ms 84592 KB Output is correct
71 Correct 1343 ms 84576 KB Output is correct
72 Correct 1350 ms 84480 KB Output is correct
73 Correct 1195 ms 81140 KB Output is correct
74 Correct 1198 ms 82148 KB Output is correct
75 Correct 1217 ms 81136 KB Output is correct
76 Correct 1196 ms 81136 KB Output is correct
77 Correct 1205 ms 81008 KB Output is correct
78 Correct 1258 ms 83824 KB Output is correct
79 Correct 931 ms 69744 KB Output is correct
80 Correct 1110 ms 84588 KB Output is correct