Submission #1189174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189174		user736482	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	1751 ms	76272 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops","inline")
//#pragma GCC target("avx2")
#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 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define POT (1<<20)
ll a,b,r,c,t,n,m,l,q,k,ak,s,pop[200007],nxt[200007];
vector<ll>pref={0},ksz;
ll sgtree[POT],sg4[POT],ans[200007];//max skok
pair<ll,ll>sg2[POT],sg3[POT];//min (wartosc,idx),suma(liczba U,liczba dodatkowych)
pair<ll,ll>add(pair<ll,ll>p1,pair<ll,ll>p2){return {p1.ff+p2.ff,p1.ss+p2.ss};}
vector<pair<pair<ll,ll>,pair<ll,ll>>>zap;
void upd(ll v,ll val){
    sgtree[v]=val;
    v/=2;
    while(v){
        sgtree[v]=max(sgtree[v*2],sgtree[v*2+1]);
        v/=2;
    }
}
ll mx(ll pocz,ll kon,ll l,ll r,ll v){
    if(pocz>r || kon<l)return -1;
    if(l>=pocz && kon>=r)return sgtree[v];
    return max(mx(pocz,kon,l,(l+r)/2,v*2),mx(pocz,kon,(l+r)/2+1,r,v*2+1));
}

ll mx4(ll pocz,ll kon,ll l,ll r,ll v){
    if(pocz>r || kon<l)return -1;
    if(l>=pocz && kon>=r)return sg4[v];
    return max(mx4(pocz,kon,l,(l+r)/2,v*2),mx4(pocz,kon,(l+r)/2+1,r,v*2+1));
}

pair<ll,ll>sm(ll pocz,ll kon,ll l,ll r,ll v){
    if(pocz>r || kon<l)return {0,0};
    if(l>=pocz && kon>=r)return sg3[v];
    return add(sm(pocz,kon,l,(l+r)/2,v*2),sm(pocz,kon,(l+r)/2+1,r,v*2+1));
}
void upd3(ll v,ll val1,ll val2){
    sg3[v]={val1,val2};
    v/=2;
    while(v){
        sg3[v]=add(sg3[v*2],sg3[v*2+1]);
        v/=2;
    }
}

pair<ll,ll>mn(ll pocz,ll kon,ll l,ll r,ll v){
    if(pocz>r || kon<l)return {INFL,-1};
    if(l>=pocz && kon>=r)return sg2[v];
    return min(mn(pocz,kon,l,(l+r)/2,v*2),mn(pocz,kon,(l+r)/2+1,r,v*2+1));
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(ll i=0;i<n;i++){
        cin>>a;
        sg4[POT/2+i]=a;
        pref.pb(pref.back()+a);
    }
    for(ll i=POT/2-1;i>0;i--)sg4[i]=max(sg4[i*2],sg4[i*2+1]);
    for(ll i=0;i<n;i++){
        cin>>a;
        sg2[POT/2+i]={a,i};
        sg3[i+POT/2]={a,0};
        ksz.pb(a);
    }
    for(ll i=POT/2-1;i>0;i--)sg2[i]=min(sg2[i*2],sg2[i*2+1]);
    for(ll i=POT/2-1;i>0;i--)sg3[i]=add(sg3[i*2],sg3[i*2]);
    for(ll i=0;i<POT;i++)sgtree[i]=-1;
    for(ll i=0;i<n;i++){
        pop[i]=mx(1,ksz[i],1,POT/2,1);
        upd(POT/2-1+ksz[i],i);
    }
    for(ll i=0;i<POT;i++)sgtree[i]=-1;
    reverse(ksz.begin(),ksz.end());
    for(ll i=0;i<n;i++){
        nxt[n-i-1]=n-1-mx(1,ksz[i]-1,1,POT/2,1);
        upd(POT/2-1+ksz[i],i);
    }
    reverse(ksz.begin(),ksz.end());
    for(ll i=0;i<n;i++){
       // cout<<pop[i]<<" "<<nxt[i]<<"\n";
    }
    for(ll i=0;i<q;i++){
        cin>>a>>b>>c;
        zap.pb({{c,i},{a,b}});
    }
    for(ll i=0;i<n;i++){
        if(pop[i]==-1){
            if(nxt[i]!=n){
                zap.pb({{pref[nxt[i]]-pref[i],-i-1},{0,ksz[i]*(pref[nxt[i]]-pref[i])}});
            }
        }
        else{
            if(nxt[i]==n){
                zap.pb({{pref[i]-pref[pop[i]],-i-1},{0,ksz[i]*(pref[i]-pref[pop[i]])}});
            }
            else{
                if(pref[i]-pref[pop[i]]<pref[nxt[i]]-pref[i])
                    zap.pb({{pref[i]-pref[pop[i]],-i-1},{0,ksz[i]*(pref[i]-pref[pop[i]])}});
                else if(pref[i]-pref[pop[i]]>pref[nxt[i]]-pref[i])
                    zap.pb({{pref[nxt[i]]-pref[i],-i-1},{0,ksz[i]*(pref[nxt[i]]-pref[i])}});
                zap.pb({{max(pref[nxt[i]]-pref[i],pref[i]-pref[pop[i]]),-i-1},{-ksz[i],ksz[i]*(pref[nxt[i]]-pref[pop[i]])}});
                
                zap.pb({{pref[nxt[i]]-pref[pop[i]],-i-1},{0,0}});
            }
        }
    }
    sort(zap.begin(),zap.end());
    for(auto i : zap){
       // cout<<i.ff.ff<<" "<<i.ff.ss<<" "<<i.ss.ff<<" "<<i.ss.ss<<"\n";
        if(i.ff.ss<0){
            upd3(-i.ff.ss+POT/2-1,i.ss.ff,i.ss.ss);
        }
        else{
            if(mx4(i.ss.ff,i.ss.ss-1,1,POT/2,1)>i.ff.ff){
                ans[i.ff.ss]=-INFL;
                continue;
            }
            i.ss.ss--;
            ll pier=mn(i.ss.ff,min(i.ss.ss,(ll)(lower_bound(pref.begin(),pref.end(),i.ff.ff+1+pref[i.ss.ff-1])-pref.begin())),1,POT/2,1).ss+1;
            ll ost=mn(max(i.ss.ff,(ll)(lower_bound(pref.begin(),pref.end(),-i.ff.ff+pref[i.ss.ss])-pref.begin()+1)),i.ss.ss,1,POT/2,1).ss+1;
            pair<ll,ll>pom=sm(pier+1,ost-1,1,POT/2,1);
            ll ansak=pom.ff*i.ff.ff+pom.ss;
            //cout<<(ll)(lower_bound(pref.begin(),pref.end(),-i.ff.ff+pref[i.ss.ss])-pref.begin()+1)<<" "<<i.ss.ss<<" "<<i.ss.ff<<" "<<min(i.ss.ss,(ll)(lower_bound(pref.begin(),pref.end(),i.ff.ff+1+pref[i.ss.ff-1])-pref.begin()-1))<<" "<<pier<<" "<<ost<<" "<<pom.ff<<"      "<<pom.ss<<"\n";
            ll pomm=(pref[i.ss.ss]-pref[ost-1]);//-max(0LL,((-i.ff.ff)*(pop[ost-1]+1>=i.ss.ff)+pref[i.ss.ss]-pref[max(pop[ost-1],i.ss.ff)]));
            if(pop[ost-1]+1>=i.ss.ff){
                pomm=min(pomm,max(0LL,pref[i.ss.ss]-pref[pop[ost-1]]-i.ff.ff));
            }
            ansak+=ksz[ost-1]*pomm;
           // cout<<ansak<<" "<<(pref[i.ss.ss]-pref[ost-1])<<"\n";
            if(pier!=ost){
                ansak+=ksz[pier-1]*min(i.ff.ff,min(pref[i.ss.ss],pref[nxt[pier-1]])-pref[pier-1]);
            }
            //cout<<ansak<<"\n";
           // for(ll i=POT/2;i<POT/2+16;i++)cout<<sg3[i].ff<<" "<<sg3[i].ss<<"   ";
           // cout<<"\n\n";
            ll akmin=INFL;
            for(ll j=i.ss.ff;j<pier;j++){
               // cout<<j<<" ";
                if(akmin>ksz[j-1]){
                    ansak+=ksz[j-1]*(pref[nxt[j-1]]-pref[j-1]);
                    akmin=ksz[j-1];
                }
            }
            ans[i.ff.ss]=ansak;
        }
    }
    for(ll i=0;i<q;i++)cout<<max(-1LL,ans[i])<<"\n";
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44