제출 #1262584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262584		user736482	Sushi (JOI16_sushi)	C++20	100 / 100	11728 ms	236284 KiB

sushi

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
#define sq 400
vector<vector<ll>>v;

ll n,q,a,b,c;
multiset<ll>s[1007],s2[1007];
vector<ll>s3[1007];

void upd(ll x){
    for(ll i : s3[x])s2[x].insert(i);
    s3[x].clear();
    for(ll i=0;i<v[x].size();i++){
        s2[x].insert(v[x][i]);
        v[x][i]=*s2[x].begin();
        s2[x].erase(s2[x].begin());
    }
    s2[x].clear();
}
ll pocz[1007],kon[1007];
int main(){
    cin>>n>>q;
    for(ll i=0;i<n;i++){
        if(i%sq==0){
            pocz[i/sq]=i;
            cin>>a;
            v.pb({a});
        }
        else{
            cin>>a;
            v.back().pb(a);
        }
        kon[i/sq]=i;
        s[i/sq].insert(a);
    }
   // cout<<v.size()<<" ";
   // for(auto j : v){
    //        for(ll k : j)cout<<k<<" ";
   //         cout<<"\n";
    //    }
   //     cout<<"\n\n";
    for(ll i=0;i<q;i++){
        cout<<flush;
        cin>>a>>b>>c;
        a--;
        b--;
        ll pc=a/sq;
        ll kn=b/sq;
        upd(pc);
        upd(kn);
       // for(auto j : v){
       //     for(ll k : j)cout<<k<<" ";
       //     cout<<"\n";
       // }
        //cout<<"\n\n";
        b-=kn*sq;
        a-=pc*sq;
        
        if(pc==kn && a<=b){
            s[pc].insert(c);
            for(ll j=a;j<=b;j++){
                if(v[pc][j]>c)swap(v[pc][j],c);

            }
            s[pc].erase(s[pc].find(c));
            cout<<c<<"\n";
            continue;
        }
        for(ll j=a;j<v[pc].size();j++){
            s[pc].insert(c);
            if(v[pc][j]>c)swap(v[pc][j],c);
            s[pc].erase(s[pc].find(c));
        }
        
        for(ll k=(pc+1)%v.size();k!=kn;k=(k+1)%v.size()){
            //cout<<k<<" ";
            s3[k].pb(c);
            s[k].insert(c);
            c=*--s[k].end();
            s[k].erase(--s[k].end());
        }
        for(ll j=0;j<=b;j++){
            s[kn].insert(c);
            if(v[kn][j]>c)swap(v[kn][j],c);
            s[kn].erase(s[kn].find(c));
        }
        cout<<c<<"\n";
    }
}

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