Submission #734776

#	Time	Username	Problem	Language	Result	Execution time	Memory
734776		abcvuitunggio	Sushi (JOI16_sushi)	C++17	100 / 100	3909 ms	78700 KiB

sushi

#include <bits/stdc++.h>
#define pq priority_queue
using namespace std;
const int sz=632;
pq <int> q[633];
pq <int, vector <int>, greater <int>> p[633];
int n,m,x[400000],s,t,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]=pq <int, vector <int>, greater <int>>();
    q[i]=pq <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);
    cin >> n >> m;
    for (int i=0;i<n;i++){
        cin >> x[i];
        q[i/sz].push(x[i]);
    }
    while (m--){
        cin >> s >> t >> cur;
        s--;
        t--;
        if (s<=t)
            f(s,t);
        else{
            f(s,n-1);
            f(0,t);
        }
        cout << cur << '\n';
    }
}

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