# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
595839 |
2022-07-14T07:34:48 Z |
이동현(#8445) |
Sushi (JOI16_sushi) |
C++17 |
|
4631 ms |
262144 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 = 632;
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);
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
504 KB |
Output is correct |
2 |
Correct |
97 ms |
516 KB |
Output is correct |
3 |
Correct |
95 ms |
512 KB |
Output is correct |
4 |
Correct |
95 ms |
512 KB |
Output is correct |
5 |
Correct |
130 ms |
500 KB |
Output is correct |
6 |
Correct |
111 ms |
468 KB |
Output is correct |
7 |
Correct |
100 ms |
500 KB |
Output is correct |
8 |
Correct |
93 ms |
468 KB |
Output is correct |
9 |
Correct |
102 ms |
520 KB |
Output is correct |
10 |
Correct |
96 ms |
516 KB |
Output is correct |
11 |
Correct |
150 ms |
508 KB |
Output is correct |
12 |
Correct |
168 ms |
520 KB |
Output is correct |
13 |
Correct |
154 ms |
504 KB |
Output is correct |
14 |
Correct |
116 ms |
516 KB |
Output is correct |
15 |
Correct |
123 ms |
516 KB |
Output is correct |
16 |
Correct |
88 ms |
500 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
4631 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
504 KB |
Output is correct |
2 |
Correct |
97 ms |
516 KB |
Output is correct |
3 |
Correct |
95 ms |
512 KB |
Output is correct |
4 |
Correct |
95 ms |
512 KB |
Output is correct |
5 |
Correct |
130 ms |
500 KB |
Output is correct |
6 |
Correct |
111 ms |
468 KB |
Output is correct |
7 |
Correct |
100 ms |
500 KB |
Output is correct |
8 |
Correct |
93 ms |
468 KB |
Output is correct |
9 |
Correct |
102 ms |
520 KB |
Output is correct |
10 |
Correct |
96 ms |
516 KB |
Output is correct |
11 |
Correct |
150 ms |
508 KB |
Output is correct |
12 |
Correct |
168 ms |
520 KB |
Output is correct |
13 |
Correct |
154 ms |
504 KB |
Output is correct |
14 |
Correct |
116 ms |
516 KB |
Output is correct |
15 |
Correct |
123 ms |
516 KB |
Output is correct |
16 |
Correct |
88 ms |
500 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Runtime error |
4631 ms |
262144 KB |
Execution killed with signal 9 |
24 |
Halted |
0 ms |
0 KB |
- |