Submission #1082031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082031		amirhoseinfar1385	Distributing Candies (IOI21_candies)	C++17	8 / 100	3559 ms	86672 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10,lg=19,kaf=(1<<lg);
long long allc[maxn];
long long inf=1e9+5;
vector<pair<long long,long long>>insq[maxn],ersq[maxn];
long long n,q;
struct segment{
    struct node{
        long long suma,ted,lazy;
        pair<long long ,long long>maxa,mina;
        node(){
            suma=ted=lazy=0;
            mina=make_pair(0,0);
            maxa=make_pair(0,0);
        }
    };
    node seg[(1<<(lg+1))];
    segment(){
        for(long long i=kaf*2-1;i>=0;i--){
            if(i>=kaf){
                seg[i].mina.first=seg[i].maxa.second=0;
                seg[i].mina.second=seg[i].maxa.second=i-kaf;
                seg[i].ted=1;
            }else{
                seg[i].ted=seg[(i<<1)].ted+seg[(i<<1)^1].ted;
                seg[i].mina.second=seg[i].maxa.second=seg[(i<<1)].maxa.second;
            }
        }
    }
    void calc(long long i){
        if(i>=kaf){
            seg[i].suma+=seg[i].lazy;
            seg[i].mina.first+=seg[i].lazy;
            seg[i].maxa.first+=seg[i].lazy;
            seg[i].lazy=0;
            return ;
        }
        seg[i].maxa=max(make_pair(seg[(i<<1)].maxa.first+seg[(i<<1)].lazy,seg[(i<<1)].maxa.second),make_pair(seg[(i<<1)^1].maxa.first+seg[(i<<1)^1].lazy,seg[(i<<1)^1].maxa.second));
        seg[i].mina=min(make_pair(seg[(i<<1)].mina.first+seg[(i<<1)].lazy,seg[(i<<1)].mina.second),make_pair(seg[(i<<1)^1].mina.first+seg[(i<<1)^1].lazy,seg[(i<<1)^1].mina.second));
    }
    void shift(long long i){
        if(i>=kaf){
            return ;
        }
        seg[(i<<1)].lazy+=seg[i].lazy;
        seg[(i<<1)^1].lazy+=seg[i].lazy;
        seg[i].lazy=0;
    }
    void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
        if(l>r||l>tr||r<tl||tl>tr){
            return ;
        }
        if(l>=tl&&r<=tr){
            seg[i].lazy+=w;
            shift(i);
            calc(i);
            return ;
        }
        long long m=(l+r)>>1;
        shift(i);
        upd((i<<1),l,m,tl,tr,w);
        upd((i<<1)^1,m+1,r,tl,tr,w);
        calc(i);
        return ;
    }
    long long porssum(long long i,long long l,long long r,long long tl,long long tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return 0;
        }
        shift(i);
        calc(i);
        if(l>=tl&&r<=tr){
            return seg[i].suma;
        }
        long long m=(l+r)>>1;
        return porssum((i<<1),l,m,tl,tr)+porssum((i<<1)^1,m+1,r,tl,tr);
    }
    pair<long long ,long long> porsmax(long long i,long long l,long long r,long long tl,long long tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return make_pair(-inf,-1);
        }
        shift(i);
        calc(i);
        if(l>=tl&&r<=tr){
            return seg[i].maxa;
        }
        long long m=(l+r)>>1;
        return max(porsmax((i<<1),l,m,tl,tr),porsmax((i<<1)^1,m+1,r,tl,tr));
    }
    pair<long long ,long long> porsmin(long long i,long long l,long long r,long long tl,long long tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return make_pair(inf,-1);
        }
        shift(i);
        calc(i);
        if(l>=tl&&r<=tr){
            return seg[i].mina;
        }
        long long m=(l+r)>>1;
        return min(porsmin((i<<1),l,m,tl,tr),porsmin((i<<1)^1,m+1,r,tl,tr));
    }
}seg;
long long tof=0;

long long solve(long long l,long long r,long long w){
    //cout<<l<<" "<<r<<" "<<w<<endl;
    if(l==r){
        //cout<<l<<" "<<r<<" "<<seg.porssum(1,0,kaf-1,q,q)<<" "<<seg.porssum(1,0,kaf-1,l,l)<<endl;
        long long res=seg.porssum(1,0,kaf-1,q,q)-seg.porssum(1,0,kaf-1,l,l);
    //    if(tof==1){
      //      res=w+res;
        //}
        if(seg.porsmax(1,0,kaf-1,l,q).second==l){
            res=w+res;
        }
        return res;
    }
    long long mid=(l+r)>>1;
    //cout<<"wtf: "<<l<<" "<<r<<" "<<seg.porsmax(1,0,kaf-1,l,r).first<<" "<<seg.porsmax(1,0,kaf-1,l,r).second<<" "<<seg.porsmin(1,0,kaf-1,l,r).first<<" "<<seg.porsmin(1,0,kaf-1,l,r).second<<endl;
    pair<long long ,long long>mx=seg.porsmax(1,0,kaf-1,l,r),mn=seg.porsmin(1,0,kaf-1,l,r);
    if(mx.first<w){
        mx.second=-1;
    }
    if(mn.first>=0){
        mn.second=-1;
    }
    if(max(mx.second,mn.second)>mid){
        if(mx.second<=mid){
            tof=0;
        }else if(mn.second<=mid){
            tof=1;
        }else if(mx.second<mn.second){
            tof=1;
        }else{
            tof=0;
        }
        return solve(mid+1,r,w);
    }
    //cout<<l<<" "<<r<<" "<<w<<endl;
    long long indmax=seg.porsmax(1,0,kaf-1,l,mid).second,indmin=seg.porsmin(1,0,kaf-1,l,mid).second;
    if(indmax>indmin){
        indmin=seg.porsmin(1,0,kaf-1,mid+1,r).second;
        //cout<<"wtffffff: "<<seg.porssum(1,0,kaf-1,indmax,indmax)<<" "<<seg.porssum(1,0,kaf-1,indmin,indmin)<<" "<<indmax<<" "<<indmin<<endl;
        if(seg.porssum(1,0,kaf-1,indmax,indmax)-seg.porssum(1,0,kaf-1,indmin,indmin)>=w){
            tof=0;
            return solve(mid+1,r,w);
        }
    }else{
        indmax=seg.porsmax(1,0,kaf-1,mid+1,r).second;
        //cout<<"wtffffff: "<<seg.porssum(1,0,kaf-1,indmax,indmax)<<" "<<seg.porssum(1,0,kaf-1,indmin,indmin)<<" "<<indmax<<" "<<indmin<<endl;
        if(seg.porssum(1,0,kaf-1,indmax,indmax)-seg.porssum(1,0,kaf-1,indmin,indmin)>=w){
            tof=1;
            return solve(mid+1,r,w);
        }
    }
    return solve(l,mid,w);
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n=c.size();
    q=l.size();
    for(long long i=0;i<n;i++){
        allc[i]=c[i];
    }
    for(long long i=0;i<q;i++){
        insq[l[i]].push_back(make_pair(i+1,v[i]));
        ersq[r[i]+1].push_back(make_pair(i+1,v[i]));
    }
    vector<int>ret;
    for(long long i=0;i<n;i++){
        tof=0;
        for(auto x:insq[i]){
            seg.upd(1,0,kaf-1,x.first,q,x.second);
        }
        for(auto x:ersq[i]){
            seg.upd(1,0,kaf-1,x.first,q,-x.second);
        }
        ret.push_back(solve(0,q,allc[i]));
    }
    return ret;
}

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