Submission #739625

#	Time	Username	Problem	Language	Result	Execution time	Memory
739625		Huseyn123	Distributing Candies (IOI21_candies)	C++17	0 / 100	593 ms	25256 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define MAX 200001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
ll n,q,t=1,m,n2,m2,k,x,y,z,x2,y2,z2,res1=0,a[MAX],b[MAX],d[MAX];
struct segtree{
    vector<int> mn,mx,lazy;
    int sz;
    void init(int n){
        sz=1;
        while(sz<n){
            sz*=2;
        }
        mn.resize(2*sz,0);
        mx.resize(2*sz,0);
        lazy.resize(2*sz,0);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1 || lazy[x]==0){
            return;
        }
        mn[2*x+1]+=lazy[x];
        mx[2*x+1]+=lazy[x];
        mn[2*x+2]+=lazy[x];
        mx[2*x+2]+=lazy[x];
        lazy[2*x+1]+=lazy[x];
        lazy[2*x+2]+=lazy[x];
        lazy[x]=0;
    }
    ll get_max(){
        return mx[0];
    }
    ll get_min(){
        return mn[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(rx<=r && lx>=l){
            mn[x]+=v;
            mx[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);
        mn[x]=min(mn[2*x+1],mn[2*x+2]);
        mx[x]=max(mx[2*x+1],mx[2*x+2]);
    }
    void upd(int l,int r,int v){
        upd(0,0,sz,l,r,v);
    }
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n = c.size();
    int q = v.size();
    vector<int> s(n);
    vector<vector<pii>> ops;
    ops.resize(n+1);
    for(int i=0;i<q;i++){
        ops[l[i]].pb(mp(1,i));
        ops[r[i]+1].pb(mp(2,i));
    }
    segtree st;
    int sum=0;
    st.init(q+1);
    for(int i=0;i<n;i++){
        for(auto x:ops[i]){
            if(x.ff==1){
                sum+=v[x.ss];
                st.upd(x.ss+1,q+1,v[x.ss]);
            }
            else{
                sum-=v[x.ss];
                st.upd(x.ss+1,q+1,-v[x.ss]);
            }
        }
        int mx,mn;
        mx=st.get_max();
        mn=st.get_min();
        int res=sum;
        if(mx-mn>c[i]){
            res-=(mx-mn-c[i]);
        }
        mn=min(mn,res);
        res-=mn;
        //cout << mx << " " << mn << " " << sum << "\n";
        s[i]=res;
    }
    return s;
}

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