Submission #200912

#	Time	Username	Problem	Language	Result	Execution time	Memory
200912		gs18115	Sushi (JOI16_sushi)	C++14	100 / 100	5367 ms	80892 KiB

sushi

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int sz=642;
int n;
int x[400010+sz];
priority_queue<int,vector<int>,less<int> >pq[sz];
priority_queue<int,vector<int>,greater<int> >rn[sz];
inline void init()
{
    for(int i=0;i<n;i++)
        pq[i/sz].ep(x[i]);
    return;
}
inline void app(int g)
{
    if(rn[g].empty())
        return;
    for(int i=g*sz;i<g*sz+sz;i++)
        if(rn[g].top()<x[i])
            rn[g].ep(x[i]),x[i]=rn[g].top(),rn[g].pop();
    while(!rn[g].empty())
        rn[g].pop();
    return;
}
inline void init(int g)
{
    while(!pq[g].empty())
        pq[g].pop();
    for(int i=g*sz;i<g*sz+sz;i++)
        pq[g].ep(x[i]);
    return;
}
inline int solve(int s,int t,int p)
{
    if(s/sz==t/sz)
    {
        app(s/sz);
        for(int i=s;i<t;i++)
            if(p<x[i])
                swap(p,x[i]);
        init(s/sz);
        return p;
    }
    int l=(s+sz-1)/sz;
    int r=t/sz;
    if(s<l*sz)
    {
        app(l-1);
        for(int i=s;i<l*sz;i++)
            if(p<x[i])
                swap(p,x[i]);
        init(l-1);
    }
    for(int i=l;i<r;i++)
    {
        if(p<pq[i].top())
        {
            int prv=p;
            p=pq[i].top();
            pq[i].pop();
            pq[i].ep(prv);
            rn[i].ep(prv);
        }
    }
    if(r*sz<t)
    {
        app(r);
        for(int i=r*sz;i<t;i++)
            if(p<x[i])
                swap(p,x[i]);
        init(r);
    }
    return p;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin>>n>>q;
    for(int i=0;i<n;i++)
        cin>>x[i];
    while(n%sz!=0)
        x[n++]=-1;
    init();
    while(q-->0)
    {
        int s,t,p;
        cin>>s>>t>>p;
        if(s>t)
            cout<<solve(0,t,solve(s-1,n,p))<<'\n';
        else
            cout<<solve(s-1,t,p)<<'\n';
    }
    cout.flush();
    return 0;
}

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