oj.uz

Submission #595989

# Submission time Handle Problem Language Result Execution time Memory
595989 2022-07-14T08:41:07 Z 이동현(#8445) Sushi (JOI16_sushi) C++17
0 / 100
 60 ms 8400 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int BS = 1000;
priority_queue<int> num[BS], numd[BS];
priority_queue<int, vector<int>, greater<int>> que[BS];
int ask[25004][3], lst[BS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int B = 800;
    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].push(a[i]);
    }
    for(int i = 0; i < q; ++i){
        cin >> ask[i][0] >> ask[i][1] >> ask[i][2];
        lst[ask[i][0] / B] = lst[ask[i][1] / B] = i;
    }
    for(int qq = 0; qq < q; ++qq){
        int x, y, k;
        x = ask[qq][0] - 1, y = ask[qq][1] - 1, k = ask[qq][2];
       // x = 0, y = n - 1, k = q + 300;
        auto sol = [&](int x, int y, int k)->int{
            auto doque = [&](int pos)->void{
                int bp = pos / B;
                if(!(int)que[bp].size()){
                    return;
                }
                int l = bp * B, r = min(n, l + B);
                for(int i = l; i < r; ++i){
                    que[bp].push(a[i]);
                    a[i] = que[bp].top();
                    que[bp].pop();
                }
                while((int)que[bp].size()) que[bp].pop();
            };
            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(xl < x) doque(x);
            if(y + 1 < yr) doque(y);
            if(x == xl) --xb, xl -= B, xr -= B;
            if(y + 1 == yr) ++yb, yl += B, yr += B;

            if(xb < yb){
                for(int i = x; i < xr; ++i){
                    if(a[i] > k){
                        numd[xb].push(a[i]);
                        swap(a[i], k);
                        num[xb].push(a[i]);
                    }
                }
                for(int i = xb + 1; i < yb; ++i){
                    if(lst[i] > qq) que[i].push(k);
                    num[i].push(k);
                    while((int)num[i].size() && num[i].top() == numd[i].top()) num[i].pop(), numd[i].pop();
                    k = num[i].top();
                    num[i].pop();
                }
                for(int i = yl; i <= y; ++i){
                    if(a[i] > k){
                        numd[yb].push(a[i]);
                        swap(a[i], k);
                        num[yb].push(a[i]);
                    }
                }
            }
            else{
                for(int i = x; i <= y; ++i){
                    if(a[i] > k){
                        numd[xb].push(a[i]);
                        swap(a[i], k);
                        num[xb].push(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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Runtime error 2 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 60 ms 8400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Runtime error 2 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -