Submission #440981

#	Time	Username	Problem	Language	Result	Execution time	Memory
440981		humbertoyusta	Distributing Candies (IOI21_candies)	C++17	29 / 100	2262 ms	41784 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline","03")
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define all(x) x.begin() , x.end()
typedef long long ll;
const ll maxn = 200010;
const ll mod = 1000000007;
const ll inf = mod * mod;

ll cap[maxn], N;

struct node{
    ll mn, mx, lazysum, set0, setmx;
    node(ll val){
        mn = val;
        mx = val;
        lazysum = 0;
        set0 = -1;
        setmx = -1;
    }
    node(){
        mn = mod;
        mx = -mod;
        lazysum = 0;
        set0 = -1;
        setmx = -1;
    }
} st[maxn*4];

void build(){
    for(int i=0; i<maxn*4; i++)
        st[i] = node(0);
}

node merge_(node a,node b){
    node c = node();
    c.mn = min( a.mn , b.mn );
    c.mx = max( a.mx , b.mx );
    return c;
}

void lazyp(ll nod,ll l,ll r){
    if( st[nod].set0 != -1 ){
        st[nod].mn = 0;
        st[nod].mx = 0;
        if( l != r ){
            st[2*nod].set0 = 1;
            st[2*nod].lazysum = 0;
            st[2*nod].setmx = -1;
            st[2*nod+1].set0 = 1;
            st[2*nod+1].lazysum = 0;
            st[2*nod+1].setmx = -1;
        }
        st[nod].set0 = -1;
    }

    if( st[nod].setmx != -1 ){
        st[nod].mn = cap[l];
        st[nod].mx = cap[r];
        if( l != r ){
            st[2*nod].setmx = 1;
            st[2*nod].lazysum = 0;
            st[2*nod].set0 = -1;
            st[2*nod+1].setmx = 1;
            st[2*nod+1].lazysum = 0;
            st[2*nod+1].set0 = -1;
        }
        st[nod].setmx = -1;
    }

    st[nod].mn += st[nod].lazysum;
    st[nod].mx += st[nod].lazysum;
    if( l != r ){
        st[2*nod].lazysum += st[nod].lazysum;
        st[2*nod+1].lazysum += st[nod].lazysum;
    }
    st[nod].lazysum = 0;
}

void sum_(ll nod,ll l,ll r,ll x,ll y,ll val){
    lazyp(nod,l,r);
    if( l > y || r < x ) return;
    if( l >= x && r <= y ){
        st[nod].lazysum += val;
        lazyp(nod,l,r);
        return;
    }
    ll mi = ( l + r ) >> 1;
        sum_(2*nod,l,mi,x,y,val);
        sum_(2*nod+1,mi+1,r,x,y,val);
    st[nod] = merge_( st[2*nod] , st[2*nod+1] );
}

void set_(int nod,int l,int r,int x,int y,int val){
    lazyp(nod,l,r);
    if( l > y || r < x ) return;
    if( l >= x && r <= y ){
        if( val == 0 ) st[nod].set0 = 1, st[nod].setmx = -1;
        if( val == 1 ) st[nod].setmx = 1, st[nod].set0 = -1;
        st[nod].lazysum = 0;
        lazyp(nod,l,r);
        return;
    }
    ll mi = ( l + r ) >> 1;
        set_(2*nod,l,mi,x,y,val);
        set_(2*nod+1,mi+1,r,x,y,val);
    st[nod] = merge_( st[2*nod] , st[2*nod+1] );
}

node get_(int nod,int l,int r,int x,int y){
    lazyp(nod,l,r);
    if( l > y || r < x ) return node();
    if( l >= x && r <= y ) return st[nod];
    ll mi = ( l + r ) >> 1;
    return merge_( get_(2*nod,l,mi,x,y) , get_(2*nod+1,mi+1,r,x,y) );
}

//void chapeo(ll nod,ll l,ll r){
//    lazyp(nod,l,r);
//    if( st[nod].mx < 0 ){
//        st[nod].lazyset = 0;
//        st[nod].lazysum = 0;
//        lazyp(nod,l,r);
//        return;
//    }
//    if( st[nod].mn > cap ){
//        st[nod].lazyset = cap;
//        st[nod].lazysum = 0;
//        lazyp(nod,l,r);
//        return;
//    }
//    if( st[nod].mn >= 0 && st[nod].mx <= cap )
//        return;
//    ll mi = ( l + r ) >> 1;
//        chapeo(2*nod,l,mi);
//        chapeo(2*nod+1,mi+1,r);
//}

//int get_fst_mn(ll nod,ll l,ll r){
//    lazyp(nod,l,r);
//    if( l == r ){
//        if( st[nod].mn < 0 ) return l;
//            else return N;
//    }
//    ll mi = ( l + r ) >> 1;
//
//    lazyp(2*nod,l,mi);
//    if( st[2*nod].mn < 0 ) return get_fst_mn(2*nod,l,mi);
//
//    lazyp(2*nod+1,mi+1,r);
//    if( st[2*nod+1].mn < 0 ) return get_fst_mn(2*nod+1,mi+1,r);
//
//    return N;
//}
//
//int get_fst_mx(int nod,int l,int r){
//    lazyp(nod,l,r);
//    if( l == r ){
//        if( st[nod].mx > cap ) return l;
//            else return N;
//    }
//    int mi = ( l + r ) >> 1;
//
//    lazyp(2*nod,l,mi);
//    if( st[2*nod].mx > cap ) return get_fst_mx(2*nod,l,mi);
//
//    lazyp(2*nod+1,mi+1,r);
//    if( st[2*nod+1].mx > cap ) return get_fst_mx(2*nod+1,mi+1,r);
//
//    return N;
//}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    ll n = c.size();
    N = n;
    ll q = l.size();

    vector<pair<int,int>> a(n);
    for(int i=0; i<n; i++){
        a[i] = { c[i] , i };
    }
    sort(all(a));
    for(int i=0; i<n; i++)
        cap[i] = a[i].f;

    build();

    for(int i=0; i<q; i++){
        //sum_(1,0,n-1,l[i],r[i],v[i]);

        if( v[i] > 0 ){
            int l = 0, r = n - 1;

            if( get_(1,0,n-1,0,0).mn + v[i] <= cap[0] ){
                sum_(1,0,n-1,0,n-1,v[i]);
                continue;
            }
            if( get_(1,0,n-1,n-1,n-1).mn + v[i] > cap[n-1] ){
                set_(1,0,n-1,0,n-1,1);
                continue;
            }

            while( l < r ){
                int mi = ( l + r ) >> 1;
                ll u = get_(1,0,n-1,mi,mi).mn;
                if( u + v[i] <= cap[mi] ) r = mi;
                    else l = mi + 1;
            }

            //db(get_(1,0,n-1,l,l).mn+v[i])db(cap[l])
            set_(1,0,n-1,0,l-1,1);
            sum_(1,0,n-1,l,n-1,v[i]);
        }

        if( v[i] < 0 ){
            int l = 0, r = n - 1;

            if( get_(1,0,n-1,0,0).mn + v[i] >= 0 ){
                sum_(1,0,n-1,0,n-1,v[i]);
                continue;
            }
            if( get_(1,0,n-1,n-1,n-1).mn + v[i] < 0 ){
                set_(1,0,n-1,0,n-1,0);
                continue;
            }

            while( l < r ){
                int mi = ( l + r ) >> 1;
                ll u = get_(1,0,n-1,mi,mi).mn;
                if( u + v[i] >= 0 ) r = mi;
                    else l = mi + 1;
            }

            //db(get_(1,0,n-1,l,l).mn+v[i])db(cap[l])
            set_(1,0,n-1,0,l-1,0);
            sum_(1,0,n-1,l,n-1,v[i]);
        }
    }

    std::vector<int> ans(n);
    for(int i=0; i<n; i++)
        ans[a[i].s] = get_(1,0,n-1,i,i).mn;

    return ans;
}

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