oj.uz

Submission #152319

# Submission time Handle Problem Language Result Execution time Memory
152319 2019-09-07T12:29:44 Z Kalam Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++11
100 / 100
 1458 ms 104128 KB 
// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 1000000 + 77 , inf = 1000000000 + 77;
int n , q , a[N] , L[N] , Fen[N];
int Ql[N] , Qr[N] , Qk[N];
int A[N];
vector < int > Q[N];
inline void Update(int x , int y) {
   x = N - x - 10;
   for(;x < N;x += x & - x)
      if(y > Fen[x])
         Fen[x] = y;
}
inline int Get(int x) {
   x = N - x - 10;
   int res = 0;
   for(;x;x ^= x & - x)
      if(res < Fen[x])
         res = Fen[x];
   return res;
}
int main() {
   a[0] = inf;
   scanf("%d %d" , & n , & q);
   for(int i = 1;i <= n;++ i) {
      scanf("%d" , a + i);
      L[i] = i - 1;
      while(a[L[i]] <= a[i]) L[i] = L[L[i]];
   }
   for(int i = 1;i <= q;++ i)
      scanf("%d %d %d" , Ql + i , Qr + i , Qk + i) , Q[Qr[i]].push_back(i);
   for(int i = 1;i <= n;++ i) {
      int x = L[i];
      if(x) Update(x , a[i] + a[x]);
      for(int id : Q[i])
         A[id] = (Get(Ql[id]) <= Qk[id]);
   }
   for(int i = 1;i <= q;++ i)
      printf("%d\n" , A[i]);
   return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:27:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d" , & n , & q);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:29:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , a + i);
       ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:34:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d" , Ql + i , Qr + i , Qk + i) , Q[Qr[i]].push_back(i);
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 23 ms 23932 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 25 ms 23988 KB Output is correct
11 Correct 26 ms 24056 KB Output is correct
12 Correct 27 ms 24124 KB Output is correct
13 Correct 28 ms 24056 KB Output is correct
14 Correct 29 ms 24284 KB Output is correct
15 Correct 28 ms 24184 KB Output is correct
16 Correct 28 ms 24312 KB Output is correct
17 Correct 27 ms 24184 KB Output is correct
18 Correct 27 ms 24184 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 103056 KB Output is correct
2 Correct 1351 ms 104128 KB Output is correct
3 Correct 1441 ms 104076 KB Output is correct
4 Correct 1370 ms 104100 KB Output is correct
5 Correct 1274 ms 100204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 30328 KB Output is correct
2 Correct 103 ms 29644 KB Output is correct
3 Correct 104 ms 29816 KB Output is correct
4 Correct 107 ms 29868 KB Output is correct
5 Correct 106 ms 30044 KB Output is correct
6 Correct 82 ms 28788 KB Output is correct
7 Correct 82 ms 28764 KB Output is correct
8 Correct 98 ms 29556 KB Output is correct
9 Correct 69 ms 27380 KB Output is correct
10 Correct 96 ms 29656 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 23 ms 23932 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 25 ms 23988 KB Output is correct
11 Correct 26 ms 24056 KB Output is correct
12 Correct 27 ms 24124 KB Output is correct
13 Correct 28 ms 24056 KB Output is correct
14 Correct 29 ms 24284 KB Output is correct
15 Correct 28 ms 24184 KB Output is correct
16 Correct 28 ms 24312 KB Output is correct
17 Correct 27 ms 24184 KB Output is correct
18 Correct 27 ms 24184 KB Output is correct
19 Correct 249 ms 39516 KB Output is correct
20 Correct 257 ms 39544 KB Output is correct
21 Correct 211 ms 37708 KB Output is correct
22 Correct 204 ms 37624 KB Output is correct
23 Correct 206 ms 37752 KB Output is correct
24 Correct 185 ms 36604 KB Output is correct
25 Correct 187 ms 36600 KB Output is correct
26 Correct 216 ms 37624 KB Output is correct
27 Correct 212 ms 37496 KB Output is correct
28 Correct 221 ms 37824 KB Output is correct
29 Correct 236 ms 38876 KB Output is correct
30 Correct 234 ms 38796 KB Output is correct
31 Correct 233 ms 38648 KB Output is correct
32 Correct 241 ms 38788 KB Output is correct
33 Correct 230 ms 38876 KB Output is correct
34 Correct 166 ms 36260 KB Output is correct
35 Correct 165 ms 36344 KB Output is correct
36 Correct 162 ms 36184 KB Output is correct
37 Correct 164 ms 36144 KB Output is correct
38 Correct 165 ms 36216 KB Output is correct
39 Correct 210 ms 37336 KB Output is correct
40 Correct 173 ms 35564 KB Output is correct
41 Correct 208 ms 36688 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 23 ms 23932 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 25 ms 23988 KB Output is correct
11 Correct 26 ms 24056 KB Output is correct
12 Correct 27 ms 24124 KB Output is correct
13 Correct 28 ms 24056 KB Output is correct
14 Correct 29 ms 24284 KB Output is correct
15 Correct 28 ms 24184 KB Output is correct
16 Correct 28 ms 24312 KB Output is correct
17 Correct 27 ms 24184 KB Output is correct
18 Correct 27 ms 24184 KB Output is correct
19 Correct 1339 ms 103056 KB Output is correct
20 Correct 1351 ms 104128 KB Output is correct
21 Correct 1441 ms 104076 KB Output is correct
22 Correct 1370 ms 104100 KB Output is correct
23 Correct 1274 ms 100204 KB Output is correct
24 Correct 113 ms 30328 KB Output is correct
25 Correct 103 ms 29644 KB Output is correct
26 Correct 104 ms 29816 KB Output is correct
27 Correct 107 ms 29868 KB Output is correct
28 Correct 106 ms 30044 KB Output is correct
29 Correct 82 ms 28788 KB Output is correct
30 Correct 82 ms 28764 KB Output is correct
31 Correct 98 ms 29556 KB Output is correct
32 Correct 69 ms 27380 KB Output is correct
33 Correct 96 ms 29656 KB Output is correct
34 Correct 249 ms 39516 KB Output is correct
35 Correct 257 ms 39544 KB Output is correct
36 Correct 211 ms 37708 KB Output is correct
37 Correct 204 ms 37624 KB Output is correct
38 Correct 206 ms 37752 KB Output is correct
39 Correct 185 ms 36604 KB Output is correct
40 Correct 187 ms 36600 KB Output is correct
41 Correct 216 ms 37624 KB Output is correct
42 Correct 212 ms 37496 KB Output is correct
43 Correct 221 ms 37824 KB Output is correct
44 Correct 236 ms 38876 KB Output is correct
45 Correct 234 ms 38796 KB Output is correct
46 Correct 233 ms 38648 KB Output is correct
47 Correct 241 ms 38788 KB Output is correct
48 Correct 230 ms 38876 KB Output is correct
49 Correct 166 ms 36260 KB Output is correct
50 Correct 165 ms 36344 KB Output is correct
51 Correct 162 ms 36184 KB Output is correct
52 Correct 164 ms 36144 KB Output is correct
53 Correct 165 ms 36216 KB Output is correct
54 Correct 210 ms 37336 KB Output is correct
55 Correct 173 ms 35564 KB Output is correct
56 Correct 208 ms 36688 KB Output is correct
57 Correct 1458 ms 102976 KB Output is correct
58 Correct 1383 ms 103004 KB Output is correct
59 Correct 1276 ms 98872 KB Output is correct
60 Correct 1395 ms 98776 KB Output is correct
61 Correct 1315 ms 98768 KB Output is correct
62 Correct 1302 ms 98252 KB Output is correct
63 Correct 881 ms 86980 KB Output is correct
64 Correct 893 ms 86900 KB Output is correct
65 Correct 1194 ms 94376 KB Output is correct
66 Correct 1191 ms 94288 KB Output is correct
67 Correct 1257 ms 94456 KB Output is correct
68 Correct 1249 ms 98864 KB Output is correct
69 Correct 1396 ms 99068 KB Output is correct
70 Correct 1416 ms 98392 KB Output is correct
71 Correct 1240 ms 97888 KB Output is correct
72 Correct 1235 ms 98304 KB Output is correct
73 Correct 767 ms 84952 KB Output is correct
74 Correct 781 ms 85900 KB Output is correct
75 Correct 880 ms 84820 KB Output is correct
76 Correct 778 ms 85148 KB Output is correct
77 Correct 774 ms 84928 KB Output is correct
78 Correct 1095 ms 92112 KB Output is correct
79 Correct 830 ms 80420 KB Output is correct
80 Correct 1020 ms 88784 KB Output is correct