Submission #734764

#	Time	Username	Problem	Language	Result	Execution time	Memory
734764		abcvuitunggio	Sushi (JOI16_sushi)	C++17	0 / 100	1570 ms	75056 KiB

sushi

#include <bits/stdc++.h>
using namespace std;
const int sz=632;
priority_queue <int> q[400000/sz];
priority_queue <int, vector <int>, greater <int>> p[400000/sz];
int n,x[400000],cur;
void reset(int i){
    for (int j=i*sz;j<min(i*sz+sz,n);j++){
        p[i].push(x[j]);
        x[j]=p[i].top();
        p[i].pop();
    }
    p[i]=priority_queue <int, vector <int>, greater <int>>();
    q[i]=priority_queue <int>();
}
void f(int l, int r){
    int b=l/sz,e=r/sz;
    reset(b);
    for (int i=l;i<min(b*sz+sz,r+1);i++)
        if (x[i]>cur)
            swap(x[i],cur);
    for (int i=b*sz;i<min(b*sz+sz,n);i++)
        q[b].push(x[i]);
    if (b==e)
        return;
    for (int i=b+1;i<e;i++){
        p[i].push(cur);
        q[i].push(cur);
        cur=q[i].top();
        q[i].pop();
    }
    reset(e);
    for (int i=e*sz;i<=r;i++)
        if (x[i]>cur)
            swap(x[i],cur);
    for (int i=e*sz;i<min(e*sz+sz,n);i++)
        q[e].push(x[i]);
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    int q,s,t,p;
    cin >> n >> q;
    for (int i=0;i<n;i++)
        cin >> x[i];
    while (q--){
        cin >> s >> t >> p;
        s--;
        t--;
        cur=p;
        if (s<=t)
            f(s,t);
        else{
            f(s,n-1);
            f(0,t);
        }
        cout << cur << '\n';
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80