oj.uz

Submission #595834

# Submission time Handle Problem Language Result Execution time Memory
595834 2022-07-14T07:27:41 Z 이동현(#8445) Sushi (JOI16_sushi) C++17
5 / 100
 5117 ms 262144 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int BS = 20004;
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;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        num[i / B].insert(a[i]);
    }
    while(q--){
        int x, y, k; cin >> x >> y >> k; --x, --y;
        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) 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:35:30: warning: unused variable 'yr' [-Wunused-variable]
   35 |             int yl = yb * B, yr = min(n, yl + B);
      |                              ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 2356 KB Output is correct
2 Correct 106 ms 2356 KB Output is correct
3 Correct 104 ms 2368 KB Output is correct
4 Correct 125 ms 2260 KB Output is correct
5 Correct 101 ms 2336 KB Output is correct
6 Correct 106 ms 2336 KB Output is correct
7 Correct 106 ms 2324 KB Output is correct
8 Correct 102 ms 2316 KB Output is correct
9 Correct 108 ms 2260 KB Output is correct
10 Correct 102 ms 2348 KB Output is correct
11 Correct 165 ms 2388 KB Output is correct
12 Correct 187 ms 2360 KB Output is correct
13 Correct 171 ms 2364 KB Output is correct
14 Correct 123 ms 2368 KB Output is correct
15 Correct 148 ms 2476 KB Output is correct
16 Correct 80 ms 2352 KB Output is correct
17 Correct 1 ms 2132 KB Output is correct
18 Correct 1 ms 2132 KB Output is correct
19 Correct 1 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 1 ms 2200 KB Output is correct
22 Correct 1 ms 2132 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5117 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 2356 KB Output is correct
2 Correct 106 ms 2356 KB Output is correct
3 Correct 104 ms 2368 KB Output is correct
4 Correct 125 ms 2260 KB Output is correct
5 Correct 101 ms 2336 KB Output is correct
6 Correct 106 ms 2336 KB Output is correct
7 Correct 106 ms 2324 KB Output is correct
8 Correct 102 ms 2316 KB Output is correct
9 Correct 108 ms 2260 KB Output is correct
10 Correct 102 ms 2348 KB Output is correct
11 Correct 165 ms 2388 KB Output is correct
12 Correct 187 ms 2360 KB Output is correct
13 Correct 171 ms 2364 KB Output is correct
14 Correct 123 ms 2368 KB Output is correct
15 Correct 148 ms 2476 KB Output is correct
16 Correct 80 ms 2352 KB Output is correct
17 Correct 1 ms 2132 KB Output is correct
18 Correct 1 ms 2132 KB Output is correct
19 Correct 1 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 1 ms 2200 KB Output is correct
22 Correct 1 ms 2132 KB Output is correct
23 Runtime error 5117 ms 262144 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -