#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int LIM = 500;
int n, q;
int arr[400002];
priority_queue<int> exist[2000]; /// 존재하는 수들의 multiset
priority_queue<int, vector<int>, greater<int> > add[2000]; /// 추가될 수들의 multiset
void remakePQ(int g){
int s = g*LIM, e = min(g*LIM+LIM-1, n-1);
while(!add[g].empty()) add[g].pop();
while(!exist[g].empty()) exist[g].pop();
for(int i=s; i<=e; i++) exist[g].push(arr[i]);
}
void resolve(int g){
int s = g*LIM, e = min(g*LIM+LIM-1, n-1);
for(int i=s; i<=e; i++){
add[g].push(arr[i]);
arr[i] = add[g].top();
add[g].pop();
}
remakePQ(g);
}
int solve(int s, int e, int v){ /// s에서 e 사이에 v를 추가한다
int sg = s/LIM, eg = e/LIM;
if(sg == eg){
resolve(sg);
for(int i=s; i<=e; i++){
if(arr[i] > v) swap(arr[i], v);
}
remakePQ(sg);
return v;
}
{ /// sg 처리
resolve(sg);
for(int i=s; i<(sg+1)*LIM; i++) if(arr[i] > v) swap(arr[i], v);
remakePQ(sg);
}
for(int i=sg+1; i<eg; i++){
add[i].push(v);
exist[i].push(v);
v = exist[i].top();
exist[i].pop();
}
{ /// sg 처리
resolve(eg);
for(int i=eg*LIM; i<=e; i++) if(arr[i] > v) swap(arr[i], v);
remakePQ(eg);
}
return v;
}
int main(){
scanf("%d %d", &n, &q);
for(int i=0; i<n; i++){
scanf("%d", &arr[i]);
}
for(int i=0; (i+1)*LIM<n; i++) remakePQ(i);
for(int i=1; i<=q; i++){
int s, e, v;
scanf("%d %d %d", &s, &e, &v);
s--, e--;
if(s<=e) printf("%d\n", solve(s, e, v));
else printf("%d\n", solve(0, e, solve(s, n-1, v)));
}
}
Compilation message
sushi.cpp: In function 'int main()':
sushi.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d %d %d", &s, &e, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
306 ms |
432 KB |
Output is correct |
2 |
Correct |
297 ms |
448 KB |
Output is correct |
3 |
Correct |
308 ms |
444 KB |
Output is correct |
4 |
Correct |
316 ms |
684 KB |
Output is correct |
5 |
Correct |
309 ms |
444 KB |
Output is correct |
6 |
Correct |
305 ms |
340 KB |
Output is correct |
7 |
Correct |
120 ms |
432 KB |
Output is correct |
8 |
Correct |
122 ms |
428 KB |
Output is correct |
9 |
Correct |
301 ms |
440 KB |
Output is correct |
10 |
Correct |
309 ms |
448 KB |
Output is correct |
11 |
Correct |
292 ms |
432 KB |
Output is correct |
12 |
Correct |
334 ms |
468 KB |
Output is correct |
13 |
Correct |
327 ms |
444 KB |
Output is correct |
14 |
Correct |
424 ms |
448 KB |
Output is correct |
15 |
Correct |
436 ms |
436 KB |
Output is correct |
16 |
Correct |
128 ms |
444 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
324 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5222 ms |
95576 KB |
Output is correct |
2 |
Correct |
5316 ms |
95368 KB |
Output is correct |
3 |
Correct |
2344 ms |
95396 KB |
Output is correct |
4 |
Correct |
5569 ms |
95468 KB |
Output is correct |
5 |
Correct |
3980 ms |
95408 KB |
Output is correct |
6 |
Correct |
5299 ms |
95440 KB |
Output is correct |
7 |
Correct |
5221 ms |
95472 KB |
Output is correct |
8 |
Correct |
5285 ms |
95628 KB |
Output is correct |
9 |
Correct |
1912 ms |
95336 KB |
Output is correct |
10 |
Correct |
4115 ms |
95360 KB |
Output is correct |
11 |
Correct |
2092 ms |
95220 KB |
Output is correct |
12 |
Correct |
4067 ms |
95504 KB |
Output is correct |
13 |
Correct |
5444 ms |
95396 KB |
Output is correct |
14 |
Correct |
5384 ms |
95512 KB |
Output is correct |
15 |
Correct |
2317 ms |
95496 KB |
Output is correct |
16 |
Correct |
5104 ms |
95444 KB |
Output is correct |
17 |
Correct |
4080 ms |
95576 KB |
Output is correct |
18 |
Correct |
5393 ms |
95540 KB |
Output is correct |
19 |
Correct |
5342 ms |
95596 KB |
Output is correct |
20 |
Correct |
5175 ms |
95580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
306 ms |
432 KB |
Output is correct |
2 |
Correct |
297 ms |
448 KB |
Output is correct |
3 |
Correct |
308 ms |
444 KB |
Output is correct |
4 |
Correct |
316 ms |
684 KB |
Output is correct |
5 |
Correct |
309 ms |
444 KB |
Output is correct |
6 |
Correct |
305 ms |
340 KB |
Output is correct |
7 |
Correct |
120 ms |
432 KB |
Output is correct |
8 |
Correct |
122 ms |
428 KB |
Output is correct |
9 |
Correct |
301 ms |
440 KB |
Output is correct |
10 |
Correct |
309 ms |
448 KB |
Output is correct |
11 |
Correct |
292 ms |
432 KB |
Output is correct |
12 |
Correct |
334 ms |
468 KB |
Output is correct |
13 |
Correct |
327 ms |
444 KB |
Output is correct |
14 |
Correct |
424 ms |
448 KB |
Output is correct |
15 |
Correct |
436 ms |
436 KB |
Output is correct |
16 |
Correct |
128 ms |
444 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
324 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
5222 ms |
95576 KB |
Output is correct |
24 |
Correct |
5316 ms |
95368 KB |
Output is correct |
25 |
Correct |
2344 ms |
95396 KB |
Output is correct |
26 |
Correct |
5569 ms |
95468 KB |
Output is correct |
27 |
Correct |
3980 ms |
95408 KB |
Output is correct |
28 |
Correct |
5299 ms |
95440 KB |
Output is correct |
29 |
Correct |
5221 ms |
95472 KB |
Output is correct |
30 |
Correct |
5285 ms |
95628 KB |
Output is correct |
31 |
Correct |
1912 ms |
95336 KB |
Output is correct |
32 |
Correct |
4115 ms |
95360 KB |
Output is correct |
33 |
Correct |
2092 ms |
95220 KB |
Output is correct |
34 |
Correct |
4067 ms |
95504 KB |
Output is correct |
35 |
Correct |
5444 ms |
95396 KB |
Output is correct |
36 |
Correct |
5384 ms |
95512 KB |
Output is correct |
37 |
Correct |
2317 ms |
95496 KB |
Output is correct |
38 |
Correct |
5104 ms |
95444 KB |
Output is correct |
39 |
Correct |
4080 ms |
95576 KB |
Output is correct |
40 |
Correct |
5393 ms |
95540 KB |
Output is correct |
41 |
Correct |
5342 ms |
95596 KB |
Output is correct |
42 |
Correct |
5175 ms |
95580 KB |
Output is correct |
43 |
Correct |
7075 ms |
8448 KB |
Output is correct |
44 |
Correct |
7183 ms |
8592 KB |
Output is correct |
45 |
Correct |
3461 ms |
8344 KB |
Output is correct |
46 |
Correct |
7452 ms |
8436 KB |
Output is correct |
47 |
Correct |
6727 ms |
8496 KB |
Output is correct |
48 |
Correct |
6721 ms |
8668 KB |
Output is correct |
49 |
Correct |
7373 ms |
8504 KB |
Output is correct |
50 |
Correct |
7195 ms |
8452 KB |
Output is correct |
51 |
Correct |
6802 ms |
8576 KB |
Output is correct |
52 |
Correct |
9043 ms |
17976 KB |
Output is correct |
53 |
Correct |
8740 ms |
17216 KB |
Output is correct |
54 |
Correct |
8135 ms |
17208 KB |
Output is correct |
55 |
Correct |
9061 ms |
17200 KB |
Output is correct |
56 |
Correct |
9004 ms |
17244 KB |
Output is correct |
57 |
Correct |
8985 ms |
17564 KB |
Output is correct |
58 |
Correct |
4343 ms |
11636 KB |
Output is correct |
59 |
Correct |
4647 ms |
11372 KB |
Output is correct |
60 |
Correct |
4372 ms |
95472 KB |
Output is correct |
61 |
Correct |
5248 ms |
95572 KB |
Output is correct |
62 |
Correct |
5188 ms |
95448 KB |
Output is correct |
63 |
Correct |
5098 ms |
95564 KB |
Output is correct |
64 |
Correct |
2281 ms |
8464 KB |
Output is correct |
65 |
Correct |
3230 ms |
50508 KB |
Output is correct |
66 |
Correct |
3265 ms |
50640 KB |
Output is correct |
67 |
Correct |
7293 ms |
77956 KB |
Output is correct |
68 |
Correct |
8150 ms |
77828 KB |
Output is correct |
69 |
Correct |
8125 ms |
77872 KB |
Output is correct |
70 |
Correct |
8064 ms |
77784 KB |
Output is correct |