oj.uz

Submission #1082061

# Submission time Handle Problem Language Result Execution time Memory
1082061 2024-08-30T16:21:35 Z amirhoseinfar1385 Distributing Candies (IOI21_candies) C++17
100 / 100
 2484 ms 93384 KB 
#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=1e15+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.second=seg[i].maxa.second=(i-kaf);
                seg[i].maxa.second*=-1;
                seg[i].ted=1;
            }else{
                seg[i].ted=seg[(i<<1)].ted+seg[(i<<1)^1].ted;
                seg[i].mina.second=seg[(i<<1)].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,long long w=0){
        shift(i);
        calc(i);
        if(l>r||l>tr||r<tl||tl>tr){
            return make_pair(-inf,-1);
        }
        if(l>=tl&&r<=tr){
            return seg[i].maxa;
        }
        long long m=(l+r)>>1;
        return max(porsmax((i<<1),l,m,tl,tr,w),porsmax((i<<1)^1,m+1,r,tl,tr,w));
    }
    pair<long long ,long long> porsmin(long long i,long long l,long long r,long long tl,long long tr,long long w=0){
        shift(i);
        calc(i);
        if(l>r||l>tr||r<tl||tl>tr){
            return make_pair(inf,-1);
        }
        if(l>=tl&&r<=tr){
            return seg[i].mina;
        }
        long long m=(l+r)>>1;
        return min(porsmin((i<<1),l,m,tl,tr,w),porsmin((i<<1)^1,m+1,r,tl,tr,w));
    }
}seg;
long long tof=0;

long long solve2(int l,int r,long long w){
    //cout<<l<<" "<<r<<" "<<w<<endl;
    pair<long long ,long long>mx=seg.porsmax(1,0,kaf-1,l+1,r),mn=seg.porsmin(1,0,kaf-1,l+1,r);
    mx.second*=-1;
    mx.first-=seg.porssum(1,0,kaf-1,l,l);
    mn.first-=seg.porssum(1,0,kaf-1,l,l);
    //cout<<mn.first<<" "<<mn.second<<endl;
    if(tof==0){
        if(mn.first<0){
            tof=0;
            return solve2(mn.second,q,w);
        }
        if(mx.first>w){
            tof=1;
            return solve2(mx.second,q,w);
        }
    }else{
        if(mn.first<-w){
            tof=0;
            return solve2(mn.second,q,w);
        }
        if(mx.first>0){
            tof=1;
            return solve2(mx.second,q,w);
        }
    }
    long long res=seg.porssum(1,0,kaf-1,q,q)-seg.porssum(1,0,kaf-1,l,l);
  //  //cout<<"chyshod: "<<l<<" "<<r<<" "<<w<<" "<<seg.porssum(1,0,kaf-1,q,q)<<" "<<seg.porssum(1,0,kaf-1,l,l)<<" "<<res<<endl;
    if(tof==1){
        res=w+res;
        tof=0;
    }
    return res;
}

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(l<q&&seg.porsmax(1,0,kaf-1,l,q).first==seg.porssum(1,0,kaf-1,l,l)){
            res=w+res;
        }
        return res;
    }
    long long mid=(l+r)>>1;
    if(seg.porsmax(1,0,kaf-1,mid+1,r).first==seg.porssum(1,0,kaf-1,mid,mid)&&seg.porsmin(1,0,kaf-1,mid+1,r).first==seg.porssum(1,0,kaf-1,mid,mid)){
        return solve(l,mid,w);
    }
    if(seg.porsmax(1,0,kaf-1,l-(l>0),mid).first==seg.porsmin(1,0,kaf-1,l-(l>0),mid).first){
        return solve(mid+1,r,w);
    }
    //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,seg.porsmax(1,0,kaf-1,mid+1,q).first).second,indmin=-seg.porsmin(1,0,kaf-1,l,mid,seg.porsmin(1,0,kaf-1,mid+1,r).first).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(solve2(0,q,allc[i]));
    }
    return ret;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 67164 KB Output is correct
2 Correct 32 ms 67156 KB Output is correct
3 Correct 33 ms 67408 KB Output is correct
4 Correct 37 ms 67376 KB Output is correct
5 Correct 40 ms 67416 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 91596 KB Output is correct
2 Correct 959 ms 90572 KB Output is correct
3 Correct 921 ms 90600 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 67160 KB Output is correct
2 Correct 345 ms 85588 KB Output is correct
3 Correct 830 ms 74596 KB Output is correct
4 Correct 1867 ms 92440 KB Output is correct
5 Correct 1701 ms 92940 KB Output is correct
6 Correct 2380 ms 93384 KB Output is correct
7 Correct 1002 ms 92684 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 67164 KB Output is correct
2 Correct 33 ms 67164 KB Output is correct
3 Correct 207 ms 80932 KB Output is correct
4 Correct 1054 ms 72832 KB Output is correct
5 Correct 1902 ms 86664 KB Output is correct
6 Correct 1869 ms 87208 KB Output is correct
7 Correct 1698 ms 87972 KB Output is correct
8 Correct 2016 ms 86444 KB Output is correct
9 Correct 612 ms 87984 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 67164 KB Output is correct
2 Correct 32 ms 67156 KB Output is correct
3 Correct 33 ms 67408 KB Output is correct
4 Correct 37 ms 67376 KB Output is correct
5 Correct 40 ms 67416 KB Output is correct
6 Correct 978 ms 91596 KB Output is correct
7 Correct 959 ms 90572 KB Output is correct
8 Correct 921 ms 90600 KB Output is correct
9 Correct 29 ms 67160 KB Output is correct
10 Correct 345 ms 85588 KB Output is correct
11 Correct 830 ms 74596 KB Output is correct
12 Correct 1867 ms 92440 KB Output is correct
13 Correct 1701 ms 92940 KB Output is correct
14 Correct 2380 ms 93384 KB Output is correct
15 Correct 1002 ms 92684 KB Output is correct
16 Correct 30 ms 67164 KB Output is correct
17 Correct 33 ms 67164 KB Output is correct
18 Correct 207 ms 80932 KB Output is correct
19 Correct 1054 ms 72832 KB Output is correct
20 Correct 1902 ms 86664 KB Output is correct
21 Correct 1869 ms 87208 KB Output is correct
22 Correct 1698 ms 87972 KB Output is correct
23 Correct 2016 ms 86444 KB Output is correct
24 Correct 612 ms 87984 KB Output is correct
25 Correct 30 ms 67412 KB Output is correct
26 Correct 813 ms 72908 KB Output is correct
27 Correct 356 ms 85336 KB Output is correct
28 Correct 1753 ms 91212 KB Output is correct
29 Correct 2133 ms 91592 KB Output is correct
30 Correct 2137 ms 91844 KB Output is correct
31 Correct 2484 ms 91852 KB Output is correct
32 Correct 2347 ms 92108 KB Output is correct