# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
595847 |
2022-07-14T07:38:41 Z |
이동현(#8445) |
Sushi (JOI16_sushi) |
C++17 |
|
12000 ms |
253548 KB |
#include <bits/stdc++.h>
using namespace std;
const int BS = 1000;
multiset<int> num[BS];
multiset<int> que[BS];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int B = 2000;
int n, q; cin >> n >> q;
//n = 400000, q = 25000;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
//a[i] = i + 1;
num[i / B].insert(a[i]);
}
while(q--){
int x, y, k; cin >> x >> y >> k; --x, --y;
//x = 0, y = n - 1, k = q + 30;
auto sol = [&](int x, int y, int k)->int{
auto doque = [&](int pos)->void{
int bp = pos / B;
int l = bp * B, r = min(n, l + B);
for(int i = l; i < r; ++i){
que[bp].insert(a[i]);
a[i] = *(que[bp].begin());
que[bp].erase(que[bp].begin());
}
que[bp].clear();
};
doque(x), doque(y);
int xb = x / B, yb = y / B;
int xl = xb * B, xr = min(n, xl + B);
int yl = yb * B, yr = min(n, yl + B);
if(xb < yb){
for(int i = x; i < xr; ++i){
if(a[i] > k){
auto p = num[xb].lower_bound(a[i]);
num[xb].erase(p);
swap(a[i], k);
num[xb].insert(a[i]);
}
}
for(int i = xb + 1; i < yb; ++i){
que[i].insert(k);
num[i].insert(k);
k = *prev(num[i].end());
assert((int)num[i].size() > 0);
num[i].erase(--num[i].end());
}
for(int i = yl; i <= y; ++i){
if(a[i] > k){
auto p = num[yb].lower_bound(a[i]);
num[yb].erase(p);
swap(a[i], k);
num[yb].insert(a[i]);
}
}
}
else{
for(int i = x; i <= y; ++i){
if(a[i] > k){
auto p = num[xb].lower_bound(a[i]);
num[xb].erase(p);
swap(a[i], k);
num[xb].insert(a[i]);
}
}
}
return k;
};
//if(x <= y) sol(x, y, k);
//else sol(0, y, sol(x, n - 1, k));
if(x <= y) cout << sol(x, y, k) << '\n';
else cout << sol(0, y, sol(x, n - 1, k)) << '\n';
}
return 0;
}
Compilation message
sushi.cpp: In lambda function:
sushi.cpp:37:30: warning: unused variable 'yr' [-Wunused-variable]
37 | int yl = yb * B, yr = min(n, yl + B);
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
348 ms |
500 KB |
Output is correct |
2 |
Correct |
371 ms |
508 KB |
Output is correct |
3 |
Correct |
342 ms |
516 KB |
Output is correct |
4 |
Correct |
364 ms |
516 KB |
Output is correct |
5 |
Correct |
333 ms |
468 KB |
Output is correct |
6 |
Correct |
360 ms |
504 KB |
Output is correct |
7 |
Correct |
333 ms |
500 KB |
Output is correct |
8 |
Correct |
331 ms |
624 KB |
Output is correct |
9 |
Correct |
349 ms |
516 KB |
Output is correct |
10 |
Correct |
380 ms |
516 KB |
Output is correct |
11 |
Correct |
449 ms |
588 KB |
Output is correct |
12 |
Correct |
495 ms |
512 KB |
Output is correct |
13 |
Correct |
403 ms |
508 KB |
Output is correct |
14 |
Correct |
484 ms |
468 KB |
Output is correct |
15 |
Correct |
468 ms |
640 KB |
Output is correct |
16 |
Correct |
235 ms |
520 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9786 ms |
253548 KB |
Output is correct |
2 |
Correct |
9828 ms |
253308 KB |
Output is correct |
3 |
Correct |
6762 ms |
253180 KB |
Output is correct |
4 |
Correct |
9522 ms |
253428 KB |
Output is correct |
5 |
Execution timed out |
12091 ms |
167064 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
348 ms |
500 KB |
Output is correct |
2 |
Correct |
371 ms |
508 KB |
Output is correct |
3 |
Correct |
342 ms |
516 KB |
Output is correct |
4 |
Correct |
364 ms |
516 KB |
Output is correct |
5 |
Correct |
333 ms |
468 KB |
Output is correct |
6 |
Correct |
360 ms |
504 KB |
Output is correct |
7 |
Correct |
333 ms |
500 KB |
Output is correct |
8 |
Correct |
331 ms |
624 KB |
Output is correct |
9 |
Correct |
349 ms |
516 KB |
Output is correct |
10 |
Correct |
380 ms |
516 KB |
Output is correct |
11 |
Correct |
449 ms |
588 KB |
Output is correct |
12 |
Correct |
495 ms |
512 KB |
Output is correct |
13 |
Correct |
403 ms |
508 KB |
Output is correct |
14 |
Correct |
484 ms |
468 KB |
Output is correct |
15 |
Correct |
468 ms |
640 KB |
Output is correct |
16 |
Correct |
235 ms |
520 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 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 |
9786 ms |
253548 KB |
Output is correct |
24 |
Correct |
9828 ms |
253308 KB |
Output is correct |
25 |
Correct |
6762 ms |
253180 KB |
Output is correct |
26 |
Correct |
9522 ms |
253428 KB |
Output is correct |
27 |
Execution timed out |
12091 ms |
167064 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |