# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
233757 |
2020-05-21T16:37:06 Z |
duality |
Fire (JOI20_ho_t5) |
C++11 |
|
330 ms |
47476 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
int S[200000];
LLI pre[200001],pre2[200001];
struct query { int T,L,R,i; };
bool comp(query a,query b) {
return a.T < b.T;
}
query queries[200000];
LLI ans[200000];
int l[200000],depth[200000];
vi SS;
vpii events[200005];
LLI bit[200001];
int main() {
int i;
int N,Q,T,L,R;
scanf("%d %d",&N,&Q);
for (i = 0; i < N; i++) scanf("%d",&S[i]);
for (i = 0; i < Q; i++) {
scanf("%d %d %d",&T,&L,&R);
queries[i] = (query){T+1,L-1,R-1,i};
}
sort(queries,queries+Q,comp);
LLI sum = 0;
for (i = 0; i < N; i++) {
while (!SS.empty() && (S[SS.back()] <= S[i])) SS.pop_back();
if (SS.empty()) l[i] = -1,depth[i] = 0;
else l[i] = SS.back(),depth[i] = depth[l[i]]+1;
SS.pb(i),sum += depth[i];
}
if (1) {
for (i = 0; i < N; i++) {
int u = i,p = 0;
while (u != -1) {
events[i-u+1].pb(mp(i,S[u]-p));
p = S[u],u = l[u];
}
}
int j = 0,k,l;
for (i = 0; i < Q; i++) {
while (j <= queries[i].T) {
for (k = 0; k < events[j].size(); k++) {
for (l = events[j][k].first+1; l <= N; l += l & (-l)) bit[l] += events[j][k].second;
}
j++;
}
LLI a = 0;
for (l = queries[i].R+1; l > 0; l -= l & (-l)) a += bit[l];
for (l = queries[i].L; l > 0; l -= l & (-l)) a -= bit[l];
ans[queries[i].i] = a;
}
for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);
return 0;
}
int j,c = 1;
int k = 0,f = 0;
for (i = 0; i < Q; i++) {
if ((i > 0) && (queries[i].T != queries[i-1].T)) f = 0;
while (queries[i].T >= 2*c) {
for (j = N-1; j >= c; j--) S[j] = max(S[j],S[j-c]);
for (j = 0; j < N; j++) pre[j+1] = pre[j]+S[j];
c *= 2;
}
int d = queries[i].T-c;
while ((k < Q) && (queries[k].T == queries[i].T)) k++;
if (!f && (k-i > 10)) {
f = 1;
for (j = 0; j < N; j++) pre2[j+1] = pre2[j]+max(S[j],(j >= d) ? S[j-d]:0);
}
if (f) ans[queries[i].i] = pre2[queries[i].R+1]-pre2[queries[i].L];
else {
LLI a = 0;
if (d > queries[i].L) a += pre[min(d,queries[i].R+1)]-pre[queries[i].L];
int e = max(d,queries[i].L);
if (e <= queries[i].R) {
int *p = S+e,*q = S+(e-d);
int t = queries[i].R-e+1;
int tt = (t/4)*4;
for (j = 0; j < tt; j += 4) {
a += (p[j] > q[j]) ? p[j]:q[j];
a += (p[j+1] > q[j+1]) ? p[j+1]:q[j+1];
a += (p[j+2] > q[j+2]) ? p[j+2]:q[j+2];
a += (p[j+3] > q[j+3]) ? p[j+3]:q[j+3];
}
for (; j < t; j++) a += (p[j] > q[j]) ? p[j]:q[j];
}
ans[queries[i].i] = a;
}
}
for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);
return 0;
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:53:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (k = 0; k < events[j].size(); k++) {
~~^~~~~~~~~~~~~~~~~~
ho_t5.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&Q);
~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:28:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < N; i++) scanf("%d",&S[i]);
~~~~~^~~~~~~~~~~~
ho_t5.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&T,&L,&R);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
8 ms |
5120 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
5248 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
10 ms |
5120 KB |
Output is correct |
10 |
Correct |
8 ms |
5120 KB |
Output is correct |
11 |
Correct |
8 ms |
5120 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
5120 KB |
Output is correct |
15 |
Correct |
7 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
5120 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Correct |
8 ms |
5120 KB |
Output is correct |
23 |
Correct |
7 ms |
5120 KB |
Output is correct |
24 |
Correct |
8 ms |
5120 KB |
Output is correct |
25 |
Correct |
7 ms |
5120 KB |
Output is correct |
26 |
Correct |
7 ms |
5120 KB |
Output is correct |
27 |
Correct |
7 ms |
5120 KB |
Output is correct |
28 |
Correct |
8 ms |
5120 KB |
Output is correct |
29 |
Correct |
8 ms |
5120 KB |
Output is correct |
30 |
Correct |
7 ms |
5120 KB |
Output is correct |
31 |
Correct |
9 ms |
5120 KB |
Output is correct |
32 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
277 ms |
41620 KB |
Output is correct |
3 |
Correct |
280 ms |
43492 KB |
Output is correct |
4 |
Correct |
277 ms |
42324 KB |
Output is correct |
5 |
Correct |
282 ms |
44384 KB |
Output is correct |
6 |
Correct |
280 ms |
43692 KB |
Output is correct |
7 |
Correct |
265 ms |
42320 KB |
Output is correct |
8 |
Correct |
277 ms |
42704 KB |
Output is correct |
9 |
Correct |
289 ms |
45476 KB |
Output is correct |
10 |
Correct |
287 ms |
42528 KB |
Output is correct |
11 |
Correct |
289 ms |
44516 KB |
Output is correct |
12 |
Correct |
284 ms |
43740 KB |
Output is correct |
13 |
Correct |
262 ms |
41948 KB |
Output is correct |
14 |
Correct |
295 ms |
45912 KB |
Output is correct |
15 |
Correct |
288 ms |
45280 KB |
Output is correct |
16 |
Correct |
288 ms |
46948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
325 ms |
43748 KB |
Output is correct |
3 |
Correct |
299 ms |
43096 KB |
Output is correct |
4 |
Correct |
330 ms |
47476 KB |
Output is correct |
5 |
Correct |
299 ms |
41568 KB |
Output is correct |
6 |
Correct |
294 ms |
43096 KB |
Output is correct |
7 |
Correct |
292 ms |
41188 KB |
Output is correct |
8 |
Correct |
286 ms |
41432 KB |
Output is correct |
9 |
Correct |
282 ms |
40392 KB |
Output is correct |
10 |
Correct |
282 ms |
40420 KB |
Output is correct |
11 |
Correct |
310 ms |
43616 KB |
Output is correct |
12 |
Correct |
303 ms |
44372 KB |
Output is correct |
13 |
Correct |
313 ms |
43952 KB |
Output is correct |
14 |
Correct |
278 ms |
40028 KB |
Output is correct |
15 |
Correct |
287 ms |
43352 KB |
Output is correct |
16 |
Correct |
289 ms |
43108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
170 ms |
17892 KB |
Output is correct |
2 |
Correct |
166 ms |
19556 KB |
Output is correct |
3 |
Correct |
171 ms |
19960 KB |
Output is correct |
4 |
Correct |
169 ms |
19428 KB |
Output is correct |
5 |
Correct |
175 ms |
19556 KB |
Output is correct |
6 |
Correct |
167 ms |
19188 KB |
Output is correct |
7 |
Correct |
173 ms |
19592 KB |
Output is correct |
8 |
Correct |
173 ms |
19428 KB |
Output is correct |
9 |
Correct |
173 ms |
19556 KB |
Output is correct |
10 |
Correct |
169 ms |
19172 KB |
Output is correct |
11 |
Correct |
177 ms |
19556 KB |
Output is correct |
12 |
Correct |
175 ms |
19680 KB |
Output is correct |
13 |
Correct |
176 ms |
19384 KB |
Output is correct |
14 |
Correct |
174 ms |
19812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
8 ms |
5120 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
5248 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
10 ms |
5120 KB |
Output is correct |
10 |
Correct |
8 ms |
5120 KB |
Output is correct |
11 |
Correct |
8 ms |
5120 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
5120 KB |
Output is correct |
15 |
Correct |
7 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
5120 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Correct |
8 ms |
5120 KB |
Output is correct |
23 |
Correct |
7 ms |
5120 KB |
Output is correct |
24 |
Correct |
8 ms |
5120 KB |
Output is correct |
25 |
Correct |
7 ms |
5120 KB |
Output is correct |
26 |
Correct |
7 ms |
5120 KB |
Output is correct |
27 |
Correct |
7 ms |
5120 KB |
Output is correct |
28 |
Correct |
8 ms |
5120 KB |
Output is correct |
29 |
Correct |
8 ms |
5120 KB |
Output is correct |
30 |
Correct |
7 ms |
5120 KB |
Output is correct |
31 |
Correct |
9 ms |
5120 KB |
Output is correct |
32 |
Correct |
7 ms |
5120 KB |
Output is correct |
33 |
Correct |
294 ms |
42208 KB |
Output is correct |
34 |
Correct |
314 ms |
44172 KB |
Output is correct |
35 |
Correct |
310 ms |
42980 KB |
Output is correct |
36 |
Correct |
296 ms |
41336 KB |
Output is correct |
37 |
Correct |
316 ms |
45152 KB |
Output is correct |
38 |
Correct |
308 ms |
44516 KB |
Output is correct |
39 |
Correct |
306 ms |
43080 KB |
Output is correct |
40 |
Correct |
287 ms |
40536 KB |
Output is correct |
41 |
Correct |
304 ms |
43236 KB |
Output is correct |
42 |
Correct |
305 ms |
42976 KB |
Output is correct |
43 |
Correct |
290 ms |
42340 KB |
Output is correct |
44 |
Correct |
287 ms |
40536 KB |
Output is correct |
45 |
Correct |
280 ms |
39780 KB |
Output is correct |
46 |
Correct |
299 ms |
44644 KB |
Output is correct |
47 |
Correct |
297 ms |
41832 KB |
Output is correct |
48 |
Correct |
297 ms |
42468 KB |
Output is correct |
49 |
Correct |
304 ms |
43620 KB |
Output is correct |
50 |
Correct |
290 ms |
41956 KB |
Output is correct |
51 |
Correct |
294 ms |
42200 KB |
Output is correct |
52 |
Correct |
296 ms |
42852 KB |
Output is correct |
53 |
Correct |
285 ms |
41568 KB |
Output is correct |
54 |
Correct |
284 ms |
41564 KB |
Output is correct |
55 |
Correct |
292 ms |
42592 KB |
Output is correct |
56 |
Correct |
302 ms |
44548 KB |
Output is correct |
57 |
Correct |
273 ms |
39388 KB |
Output is correct |
58 |
Correct |
285 ms |
40548 KB |
Output is correct |
59 |
Correct |
277 ms |
41620 KB |
Output is correct |
60 |
Correct |
280 ms |
43492 KB |
Output is correct |
61 |
Correct |
277 ms |
42324 KB |
Output is correct |
62 |
Correct |
282 ms |
44384 KB |
Output is correct |
63 |
Correct |
280 ms |
43692 KB |
Output is correct |
64 |
Correct |
265 ms |
42320 KB |
Output is correct |
65 |
Correct |
277 ms |
42704 KB |
Output is correct |
66 |
Correct |
289 ms |
45476 KB |
Output is correct |
67 |
Correct |
287 ms |
42528 KB |
Output is correct |
68 |
Correct |
289 ms |
44516 KB |
Output is correct |
69 |
Correct |
284 ms |
43740 KB |
Output is correct |
70 |
Correct |
262 ms |
41948 KB |
Output is correct |
71 |
Correct |
295 ms |
45912 KB |
Output is correct |
72 |
Correct |
288 ms |
45280 KB |
Output is correct |
73 |
Correct |
288 ms |
46948 KB |
Output is correct |
74 |
Correct |
325 ms |
43748 KB |
Output is correct |
75 |
Correct |
299 ms |
43096 KB |
Output is correct |
76 |
Correct |
330 ms |
47476 KB |
Output is correct |
77 |
Correct |
299 ms |
41568 KB |
Output is correct |
78 |
Correct |
294 ms |
43096 KB |
Output is correct |
79 |
Correct |
292 ms |
41188 KB |
Output is correct |
80 |
Correct |
286 ms |
41432 KB |
Output is correct |
81 |
Correct |
282 ms |
40392 KB |
Output is correct |
82 |
Correct |
282 ms |
40420 KB |
Output is correct |
83 |
Correct |
310 ms |
43616 KB |
Output is correct |
84 |
Correct |
303 ms |
44372 KB |
Output is correct |
85 |
Correct |
313 ms |
43952 KB |
Output is correct |
86 |
Correct |
278 ms |
40028 KB |
Output is correct |
87 |
Correct |
287 ms |
43352 KB |
Output is correct |
88 |
Correct |
289 ms |
43108 KB |
Output is correct |
89 |
Correct |
170 ms |
17892 KB |
Output is correct |
90 |
Correct |
166 ms |
19556 KB |
Output is correct |
91 |
Correct |
171 ms |
19960 KB |
Output is correct |
92 |
Correct |
169 ms |
19428 KB |
Output is correct |
93 |
Correct |
175 ms |
19556 KB |
Output is correct |
94 |
Correct |
167 ms |
19188 KB |
Output is correct |
95 |
Correct |
173 ms |
19592 KB |
Output is correct |
96 |
Correct |
173 ms |
19428 KB |
Output is correct |
97 |
Correct |
173 ms |
19556 KB |
Output is correct |
98 |
Correct |
169 ms |
19172 KB |
Output is correct |
99 |
Correct |
177 ms |
19556 KB |
Output is correct |
100 |
Correct |
175 ms |
19680 KB |
Output is correct |
101 |
Correct |
176 ms |
19384 KB |
Output is correct |
102 |
Correct |
174 ms |
19812 KB |
Output is correct |