Submission #1290805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290805		user736482	Distributing Candies (IOI21_candies)	C++20	100 / 100	429 ms	33260 KiB

candies

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
ll fct[1000007];
ll fp(ll a,ll b){
    ll c=1;while(b){if(b&1)c=(c*a)%MOD;a=(a*a)%MOD;b/=2;}
    return c;
}
ll iv(ll a){
    return fp(a,MOD-2);
}
ll bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return ((fct[a]*iv(fct[b]))%MOD*iv(fct[a-b]))%MOD;
}
ll mn[POT],mx[POT];
ll lz[POT];
void pusz(ll v){
    mn[v*2]+=lz[v];
    mx[v*2]+=lz[v];
    lz[v*2]+=lz[v];
    lz[v*2+1]+=lz[v];
    mx[v*2+1]+=lz[v];
    mn[v*2+1]+=lz[v];
    lz[v]=0;
}
void pull(ll v){
    mn[v]=min(mn[v*2],mn[v*2+1]);
    mx[v]=max(mx[v*2],mx[v*2+1]);
}
void add(ll v,ll l,ll r,ll pocz,ll kon,ll x){
    //cout<<v<<" "<<l<<" "<<r<<" "<<pocz<<" "<<kon<<"\n"<<flush;
    if(l>kon || r<pocz)return;
    if(l>=pocz && r<=kon){
        mn[v]+=x;
        mx[v]+=x;
        lz[v]+=x;
        return;
    }
    pusz(v);
    add(v*2,l,(l+r)/2,pocz,kon,x);
    add(v*2+1,(l+r)/2+1,r,pocz,kon,x);
    pull(v);

}
ll gt(ll v){
    v+=POT/2-1;
    ll v2=v;
    vi p;
    v/=2;
    while(v){
        p.pb(v);v/=2;
    }
    while(p.size()){
        pusz(p.back());
        p.pop_back();
    }
    return mn[v2];
}
ll frt(ll v,ll l,ll r,ll x,ll mal,ll duz){
    
    if(l==r)return l;
    pusz(v);
   // cout<<v<<" "<<l<<" "<<r<<" "<<x<<" "<<mal<<" "<<duz<<" "<<mn[v*2+1]<<" "<<mx[v*2+1]<<"\n";
    if(max(duz,mx[v*2+1])-min(mal,mn[v*2+1])>=x)return frt(v*2+1,(l+r)/2+1,r,x,mal,duz);
    return frt(v*2,l,(l+r)/2,x,min(mal,mn[v*2+1]),max(duz,mx[v*2+1]));
}
ll mnn(ll v,ll pocz,ll kon,ll l,ll r){
    if(l>kon || r<pocz)return INFL;
    if(l>=pocz && r<=kon)return mn[v];
    pusz(v);
    return min(mnn(v*2,pocz,kon,l,(l+r)/2),mnn(v*2+1,pocz,kon,(l+r)/2+1,r));
}
ll mxx(ll v,ll pocz,ll kon,ll l,ll r){
    if(l>kon || r<pocz)return -INFL;
    if(l>=pocz && r<=kon)return mx[v];
    pusz(v);
    return max(mxx(v*2,pocz,kon,l,(l+r)/2),mxx(v*2+1,pocz,kon,(l+r)/2+1,r));
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
    ll n=c.size();
    l.insert(l.begin(),0);
    r.insert(r.begin(),n-1);
    v.insert(v.begin(),-INF);
    ll q=l.size();
    ll sm=0;
    vii op[n+1];
    for(ll i=0;i<q;i++){
        op[l[i]].pb({i,v[i]});
        op[r[i]+1].pb({i,-v[i]});
    }
    vector<int>ans;
    for(ll i=0;i<n;i++){
        for(auto j : op[i]){
            add(1,1,POT/2,j.ff+1,POT/2,j.ss);
            sm+=j.ss;   
        }
        ll x=frt(1,1,POT/2,c[i],INFL,-INFL);
        ll du=mxx(1,x,POT/2,1,POT/2);
        ll ma=mnn(1,x,POT/2,1,POT/2);
        if(du-gt(x)>=c[i]){
            ans.pb(c[i]-du+sm);
        }
        else{
            ans.pb(sm-ma);
        }
    }
    return ans;
}

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