Submission #1201709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201709		8pete8	Distributing Candies (IOI21_candies)	C++20	67 / 100	1297 ms	47000 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define s second
#define pb push_back
#define f first
#define all(x) x.begin(),x.end()
const int mxn=2e5,inf=1e18,minf=-1e18;
int n,q;
int C[mxn+10],L[mxn+10],R[mxn+10],V[mxn+10];
struct sub1{
    static vector<int32_t>solve(){
        vector<int32_t>ans(n,0);
        for(int i=0;i<q;i++){
            for(int j=L[i];j<=R[i];j++)ans[j]+=V[i];
            for(int j=0;j<n;j++)ans[j]=max(0,ans[j]),ans[j]=min(ans[j],(int32_t)C[j]);
        }
        return ans;
    }
};
struct sub2{
    struct fen{
        int fwk[mxn+10];
        void init(){for(int i=0;i<=n;i++)fwk[i]=0;}
        void update(int pos,int val){
            pos++;
            for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;
        }
        int qry(int pos){
            int sum=0;
            pos++;
            if(pos<=0)return 0;
            for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
            if(sum<0)assert(0);
            return sum;
        }
    };
    static vector<int32_t>solve(){
        fen t;
        t.init();
        vector<int32_t>ans(n,0);
        int sum=0;
        for(int i=0;i<q;i++){
            t.update(L[i],V[i]);
            t.update(R[i]+1,-V[i]);
        }
        for(int i=0;i<n;i++){
            int x=min(C[i],t.qry(i));
            ans[i]=(int32_t)x;
        }
        return ans;
    }
};
int mn[4*mxn+10],mn2[4*mxn+10];
int lazy[4*mxn+10],O[4*mxn+10];
int tag1[4*mxn+10],tag2[4*mxn+10];
struct seg{

    //original array
    //lazy , get min , set to 0 , set to C[i]
    //qry for the prefix <0
    void pull(int pos){
        mn[pos]=min(mn[pos<<1],mn[pos<<1|1]);
        mn2[pos]=min(mn2[pos<<1],mn2[pos<<1|1]);
    }
    void build(int pos=1,int l=0,int r=n-1){
        if(l==r){
            O[pos]=C[l];
            mn2[pos]=O[pos];
            return;
        }
        mn[pos]=0;
        tag1[pos]=lazy[pos]=tag2[pos]=0;
        int mid=l+(r-l)/2;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
        pull(pos);
        O[pos]=min(O[pos<<1],O[pos<<1|1]);
    }
    void apply1(int x,int pos){
        mn[pos]+=x;
        mn2[pos]-=x;
        lazy[pos]+=x;
    }
    void apply2(int x,int pos){
        if(!x)return;
        //tag1
        mn[pos]=0;
        mn2[pos]=O[pos];
        tag2[pos]=lazy[pos]=0;
        tag1[pos]=1;
    }
    void apply3(int x,int pos){
        if(!x)return;
        mn[pos]=O[pos];
        mn2[pos]=0;
        tag1[pos]=lazy[pos]=0;
        tag2[pos]=1;
    }
    void push(int pos,int l,int r){
        if(l!=r){
            apply2(tag1[pos],pos<<1);
            apply2(tag1[pos],pos<<1|1);

            apply3(tag2[pos],pos<<1);
            apply3(tag2[pos],pos<<1|1);

            apply1(lazy[pos],pos<<1);
            apply1(lazy[pos],pos<<1|1);
        }
        lazy[pos]=tag1[pos]=tag2[pos]=0;
    }
    void update1(int ql,int qr,int val,int pos=1,int l=0,int r=n-1){
        if(ql>r||qr<l)return;
        if(ql<=l&&r<=qr)return void(apply1(val,pos));
        int mid=l+(r-l)/2;
        push(pos,l,r);
        update1(ql,qr,val,pos<<1,l,mid);
        update1(ql,qr,val,pos<<1|1,mid+1,r);
        pull(pos);
    }
    void update2(int ql,int qr,int val=1,int pos=1,int l=0,int r=n-1){
        if(ql>r||qr<l)return;
        if(ql<=l&&r<=qr)return void(apply2(val,pos));
        int mid=l+(r-l)/2;
        push(pos,l,r);
        update2(ql,qr,val,pos<<1,l,mid);
        update2(ql,qr,val,pos<<1|1,mid+1,r);
        pull(pos);
    }
    void update3(int ql,int qr,int val=1,int pos=1,int l=0,int r=n-1){
        if(ql>r||qr<l)return;
        if(ql<=l&&r<=qr)return void(apply3(val,pos));
        int mid=l+(r-l)/2;
        push(pos,l,r);
        update3(ql,qr,val,pos<<1,l,mid);
        update3(ql,qr,val,pos<<1|1,mid+1,r);
        pull(pos);
    }
    int qry1(int ql,int qr,int pos=1,int l=0,int r=n-1){
        if(ql>r||qr<l)return inf;
        if(ql<=l&&r<=qr)return mn[pos];
        int mid=l+(r-l)/2;
        push(pos,l,r);
        return min(qry1(ql,qr,pos<<1,l,mid),qry1(ql,qr,pos<<1|1,mid+1,r));
    }
    int qry2(int ql,int qr,int pos=1,int l=0,int r=n-1){
        if(ql>r||qr<l)return inf;
        if(ql<=l&&r<=qr)return mn2[pos];
        int mid=l+(r-l)/2;
        push(pos,l,r);
        return min(qry2(ql,qr,pos<<1,l,mid),qry2(ql,qr,pos<<1|1,mid+1,r));
    }
};
struct sub4{
    static vector<int32_t>solve(){
        vector<int32_t>ans(n);
        vector<pii>ord;
        seg t;
        for(int i=0;i<n;i++)ord.pb({C[i],i});
        sort(C,C+n);
        sort(all(ord));
        t.build();
        for(int i=0;i<q;i++){
            t.update1(L[i],R[i],V[i]);
            int pos=-1;
            int l=0,r=n-1;
            while(l<=r){
                int mid=l+(r-l)/2;
                if(t.qry1(mid,mid)<0)l=mid+1,pos=max(pos,mid);
                else r=mid-1;
            }
            if(pos!=-1)t.update2(0,pos);
            l=0,r=n-1,pos=-1;
            while(l<=r){
                int mid=l+(r-l)/2;
                if(t.qry2(mid,mid)<0)l=mid+1,pos=max(pos,mid);
                else r=mid-1;
            }
            if(pos!=-1)t.update3(0,pos);
        }
        for(int i=0;i<n;i++){
            ans[ord[i].s]=t.qry1(i,i);
        }
        return ans;
    }
};
int sum[4*mxn+10];
int mx1[4*mxn+10],mx2[4*mxn+10],mxc[4*mxn+10],mn1[4*mxn+10],mnc[4*mxn+10];
struct segbeat{
    //min,max,add
    //chmin
    void apply1(int pos, int x,int l,int r){
        if(mx1[pos]<=x)return;
        //mx2[pos] <= x < mx1[pos] ->update only mx1[pos]
        sum[pos]-=mx1[pos]*mxc[pos];
        mx1[pos]=x;
        sum[pos]+=mx1[pos]*mxc[pos];
        if(l==r)mn1[pos]=x;
        else{
            //case mx1 intersects mn1,mn2
            if(x<=mn1[pos])mn1[pos]=x;
            else if(x<mn2[pos])mn2[pos]=x;
        }
        //lazy[pos]=0;
    }
    void apply2(int pos, int x,int l,int r){
        if(mn1[pos]>=x)return;
        //mn1[pos] <= x < mn2[pos]
        sum[pos]-=mn1[pos]*mnc[pos];
        mn1[pos]=x;
        sum[pos]+=mn1[pos]*mnc[pos];
        if(l==r)mx1[pos]=x;
        else{
            if(x>=mx1[pos])mx1[pos]=x;
            else if(x>mx2[pos])mx2[pos]=x;
        }
        //lazy[pos]=0;
    }
    void apply3(int pos,int x,int l,int r){
        sum[pos]+=(r-l+1)*x;
        mx1[pos]+=x;
        if(mx2[pos]!=minf)mx2[pos]+=x;
        mn1[pos]+=x;
        if(mn2[pos]!=inf)mn2[pos]+=x;
        lazy[pos]+=x;
    }
    void push(int pos,int l,int r){
        if(l!=r){
            int mid=l+(r-l)/2;
            apply3(pos<<1,lazy[pos],l,mid);
            apply3(pos<<1|1,lazy[pos],mid+1,r);

            apply1(pos<<1,mx1[pos],l,mid);
            apply1(pos<<1|1,mx1[pos],mid+1,r);
            
            apply2(pos<<1,mn1[pos],l,mid);
            apply2(pos<<1|1,mn1[pos],mid+1,r);
        }
        lazy[pos]=0;
    }
    void pull(int pos,int l,int r){
        sum[pos]=sum[pos<<1]+sum[pos<<1|1];

        if(mx1[pos<<1]==mx1[pos<<1|1]){
            mx1[pos]=mx1[pos<<1];
            mx2[pos]=max(mx2[pos<<1],mx2[pos<<1|1]);
            mxc[pos]=mxc[pos<<1]+mxc[pos<<1|1];
        }
        else{
            if(mx1[pos<<1]>mx1[pos<<1|1]){
                mx1[pos]=mx1[pos<<1];
                mx2[pos]=max(mx1[pos<<1|1],mx2[pos<<1]);
                mxc[pos]=mxc[pos<<1];
            }
            else{
                mx1[pos]=mx1[pos<<1|1];
                mx2[pos]=max(mx1[pos<<1],mx2[pos<<1|1]);
                mxc[pos]=mxc[pos<<1|1];
            }
        }

        if(mn1[pos<<1]==mn1[pos<<1|1]){
            mn1[pos]=mn1[pos<<1];
            mn2[pos]=min(mn2[pos<<1],mn2[pos<<1|1]);
            mnc[pos]=mnc[pos<<1]+mnc[pos<<1|1];
        }
        else{
            if(mn1[pos<<1]<mn1[pos<<1|1]){
                mn1[pos]=mn1[pos<<1];
                mn2[pos]=min(mn1[pos<<1|1],mn2[pos<<1]);
                mnc[pos]=mnc[pos<<1];
            }
            else{
                mn1[pos]=mn1[pos<<1|1];
                mn2[pos]=min(mn1[pos<<1],mn2[pos<<1|1]);
                mnc[pos]=mnc[pos<<1|1];
            }
        }
    }
    void build(int pos=1,int l=0,int r=n-1){
        lazy[pos]=0;
        if(l==r){
            sum[pos]=mx1[pos]=mn1[pos]=0;
            mx2[pos]=minf;
            mn2[pos]=inf;
            mnc[pos]=mxc[pos]=1;
            return;
        }
        int mid=l+(r-l)/2;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
        pull(pos,l,r);
    }
    //chmin
    void update1(int ql,int qr,int x,int pos=1,int l=0,int r=n-1){
        if(l>qr||r<ql||mx1[pos]<=x)return;
        if(ql<=l&&r<=qr&&mx2[pos]<x)return void(apply1(pos,x,l,r));
        int mid=l+(r-l)/2;
        push(pos,l,r);
        update1(ql,qr,x,pos<<1,l,mid);
        update1(ql,qr,x,pos<<1|1,mid+1,r);
        pull(pos,l,r);
    }
    void update2(int ql,int qr,int x,int pos=1,int l=0,int r=n-1){
        if(l>qr||r<ql||mn1[pos]>=x)return;
        if(ql<=l&&r<=qr&&mn2[pos]>x)return void(apply2(pos,x,l,r));
        int mid=l+(r-l)/2;
        push(pos,l,r);
        update2(ql,qr,x,pos<<1,l,mid);
        update2(ql,qr,x,pos<<1|1,mid+1,r);
        pull(pos,l,r);
    }
    void update3(int ql,int qr,int x,int pos=1,int l=0,int r=n-1){
        if(l>qr||r<ql)return;
        if(ql<=l&&r<=qr)return void(apply3(pos,x,l,r));
        int mid=l+(r-l)/2;
        push(pos,l,r);
        update3(ql,qr,x,pos<<1,l,mid);
        update3(ql,qr,x,pos<<1|1,mid+1,r);
        pull(pos,l,r);
    }
    int qry(int ql,int qr,int pos=1,int l=0,int r=n-1){
        if(l>qr||r<ql)return 0;
        if(ql<=l&&r<=qr)return sum[pos];
        int mid=l+(r-l)/2;
        push(pos,l,r);
        return qry(ql,qr,pos<<1,l,mid)+qry(ql,qr,pos<<1|1,mid+1,r);
    }
};
struct sub3{
    static vector<int32_t>solve(){
        segbeat t;
        t.build();
        for(int i=0;i<q;i++){
            t.update3(L[i],R[i],V[i]);
            t.update1(L[i],R[i],C[0]);
            t.update2(L[i],R[i],0);
        }
        vector<int32_t>ans;
        for(int i=0;i<n;i++)ans.pb(t.qry(i,i));
        return ans;
    }
};
vector<int32_t> distribute_candies(vector<int32_t> c,vector<int32_t> l,vector<int32_t> r,vector<int32_t> v) {
    n=c.size(),q=l.size();
    for(int i=0;i<n;i++)C[i]=c[i];
    for(int i=0;i<q;i++)L[i]=l[i],R[i]=r[i],V[i]=v[i];
    int yes=1,yes2=1;
    for(auto i:v)if(i<0)yes=0;
    for(int i=0;i<q;i++)yes2&=(l[i]==0&&r[i]==n-1);
    if(n<=2000&&q<=2000)return sub1::solve();
    else if(yes)return sub2::solve();
    else if(yes2)return sub4::solve();
    else return sub3::solve();
}

/*
10
11 440 51 41 11 1 3 108 148 14
10
0 9 60
0 9 -9
0 9 -30
0 9 41
0 9 82
0 9 69
0 9 -79
0 9 -39
0 9 72
0 9 41
*/

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33