제출 #1055274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055274		Huseyn123	사탕 분배 (IOI21_candies)	C++17	100 / 100	2126 ms	47208 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
#define INF LLONG_MAX
#define pb push_back
using namespace std;
typedef long long ll;
vector<vector<int>> s,e;
struct segtree_min{
    vector<ll> mins;
    vector<ll> lazy;
    int size;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        mins.assign(2*size,0LL);
        lazy.assign(2*size,0LL);
    }
    void build(int x,int lx,int rx,vector<int> &a){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                mins[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(2*x+1,lx,m,a);
        build(2*x+2,m,rx,a);
        mins[x]=min(mins[2*x+1],mins[2*x+2]);
    }
    void build(vector<int> &a){
        build(0,0,size,a);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1){
            return;
        }
        mins[2*x+1]+=lazy[x];
        mins[2*x+2]+=lazy[x];
        lazy[2*x+1]+=lazy[x];
        lazy[2*x+2]+=lazy[x];
        lazy[x]=0;
    }
    void upd(int x,int lx,int rx,int l,int r,int v){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return;
        }
        if(lx>=l && rx<=r){
            mins[x]+=v;
            lazy[x]+=v;
            return;
        }
        int m=(lx+rx)/2;
        upd(2*x+1,lx,m,l,r,v);
        upd(2*x+2,m,rx,l,r,v);
        mins[x]=min(mins[2*x+1],mins[2*x+2]);
    }
    void upd(int l,int r,int v){
        return upd(0,0,size,l,r,v);
    }
    ll get(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return INF;
        }
        if(lx>=l && rx<=r){
            return mins[x];
        }
        int m=(lx+rx)/2;
        ll s1,s2;
        s1=get(2*x+1,lx,m,l,r);
        s2=get(2*x+2,m,rx,l,r);
        return min(s1,s2);
    }
    ll get(int l,int r){
        return get(0,0,size,l,r);
    }
};
struct segtree_max{
    vector<ll> maxs;
    vector<ll> lazy;
    int size;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        maxs.assign(2*size,0LL);
        lazy.assign(2*size,0LL);
    }
    void build(int x,int lx,int rx,vector<int> &a){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                maxs[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(2*x+1,lx,m,a);
        build(2*x+2,m,rx,a);
        maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
    }
    void build(vector<int> &a){
        build(0,0,size,a);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1){
            return;
        }
        maxs[2*x+1]+=lazy[x];
        maxs[2*x+2]+=lazy[x];
        lazy[2*x+1]+=lazy[x];
        lazy[2*x+2]+=lazy[x];
        lazy[x]=0;
    }
    void upd(int x,int lx,int rx,int l,int r,int v){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return;
        }
        if(lx>=l && rx<=r){
            maxs[x]+=v;
            lazy[x]+=v;
            return;
        }
        int m=(lx+rx)/2;
        upd(2*x+1,lx,m,l,r,v);
        upd(2*x+2,m,rx,l,r,v);
        maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
    }
    void upd(int l,int r,int v){
        return upd(0,0,size,l,r,v);
    }
    ll get(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return -INF;
        }
        if(lx>=l && rx<=r){
            return maxs[x];
        }
        int m=(lx+rx)/2;
        ll s1,s2;
        s1=get(2*x+1,lx,m,l,r);
        s2=get(2*x+2,m,rx,l,r);
        return max(s1,s2);
    }
    ll get(int l,int r){
        return get(0,0,size,l,r);
    }
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<int> ans(n);
    s.resize(n);
    e.resize(n);
    for(int i=0;i<q;i++){
        s[l[i]].pb(i); 
        e[r[i]].pb(i);
    }
    segtree_min stmin;
    segtree_max stmax;
    stmin.init(q); 
    stmax.init(q);
    for(int i=0;i<n;i++){
        for(auto x:s[i]){
            stmin.upd(x,q,v[x]);
            stmax.upd(x,q,v[x]);
        }
        int l,r,mid; 
        l=0; 
        r=q-1; 
        while(l<r){
            mid=(l+r+1)/2;
            if(stmax.get(mid,q)-stmin.get(mid,q)>=c[i]){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        ll res=0;
        if(stmax.get(l,q)-stmin.get(l,q)>=c[i]){
            if(stmax.get(l,l+1)==stmax.get(l,q)){
                res=-stmin.get(l,q);
                if(l+1<q){
                    ll mx=stmax.get(l+1,q);
                    if(res+mx>c[i]){
                        res=c[i]-mx;
                    }
                }
            }
            else{
                res=c[i]-stmax.get(l,q);
                if(l+1<q){
                    ll mn=stmin.get(l+1,q);
                    if(res+mn<0){
                        res=-mn;
                    }
                }
            }
        }
        else{
            ll mx=stmax.get(0,q);
            ll mn=stmin.get(0,q);
            if(mx>c[i]){
                res=c[i]-mx;
            }
            if(mn<0){
                res=-mn;
            }
        }
        ans[i]=res+stmax.get(q-1,q);
        for(auto x:e[i]){
            stmin.upd(x,q,-v[x]);
            stmax.upd(x,q,-v[x]);
        }
    }
    /*
        ll val[q+1];
        pair<ll,ll> mn[q+1],mx[q+1];
        val[0]=0;
        for(int i=1;i<=q;i++){
            val[i]=v[i-1];
            val[i]+=val[i-1];
        }
        mn[q]={val[q],q}; 
        mx[q]={val[q],q};
        for(int i=q-1;i>=1;i--){
            mn[i]={val[i],(ll)i};
            mx[i]={val[i],(ll)i};
            if(mn[i+1].first<=val[i]){
                mn[i]=mn[i+1];
            }
            if(mx[i+1].first>=val[i]){
                mx[i]=mx[i+1];
            }
        }
        int ind=1;
        while(ind<=q){
            e.push_back({mx[ind].first-mn[ind].first,mx[ind].second,mn[ind].second});
            ind=max(mx[ind].second,mn[ind].second)+1;
        }
        int sz=(int)e.size();
        for(int i=0;i<n;i++){
            int l,r,mid;
            l=0; 
            r=sz-1;
            while(l<r){
                mid=(l+r)/2; 
                if(e[mid][0]<c[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            ll res=0;
            if(e[l][0]<c[i]){
                if(l){
                    if(e[l-1][1]>e[l-1][2]){
                        res+=c[i]-val[e[l-1][1]];
                    }
                    else{
                        res-=val[e[l-1][2]];
                    }
                }
                if(val[e[l][1]]+res>c[i]){
                    res=c[i]-val[e[l][1]];
                }
                if(val[e[l][2]]+res<0){
                    res=-val[e[l][2]];
                }
            }
            else{
                if(e[sz-1][1]>e[sz-1][2]){
                    res+=c[i]-val[e[sz-1][1]];
                }
                else{
                    res-=val[e[sz-1][2]];
                }
            }
            s[i]=val[q]+res;
        }
    */
    return ans;
}

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