Submission #440968

#	Time	Username	Problem	Language	Result	Execution time	Memory
440968		humbertoyusta	Distributing Candies (IOI21_candies)	C++17	0 / 100	1136 ms	19880 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()
const int maxn = 200010;
const int mod = 1000000007;
const int inf = 1000000007;

int cap, N;

struct node{
    int mn, mx, lazysum, lazyset;
    node(int val){
        mn = val;
        mx = val;
        lazysum = 0;
        lazyset = -1;
    }
    node(){
        mn = mod;
        mx = -mod;
        lazysum = 0;
        lazyset = -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(int nod,int l,int r){
    if( st[nod].lazyset != -1 ){
        st[nod].mn = st[nod].lazyset;
        st[nod].mx = st[nod].lazyset;
        if( l != r ){
            st[2*nod].lazyset = st[nod].lazyset;
            st[2*nod].lazysum = 0;
            st[2*nod+1].lazyset = st[nod].lazyset;
            st[2*nod+1].lazysum = 0;
        }
        st[nod].lazyset = -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_(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 ){
        st[nod].lazysum += val;
        lazyp(nod,l,r);
        return;
    }
    int 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 ){
        st[nod].lazyset = val;
        st[nod].lazysum = 0;
        lazyp(nod,l,r);
        return;
    }
    int 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];
    int mi = ( l + r ) >> 1;
    return merge_( get_(2*nod,l,mi,x,y) , get_(2*nod+1,mi+1,r,x,y) );
}

void chapeo(int nod,int l,int 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;
    int mi = ( l + r ) >> 1;
        chapeo(2*nod,l,mi);
        chapeo(2*nod+1,mi+1,r);
}

int get_fst_mn(int nod,int l,int r){
    lazyp(nod,l,r);
    if( l == r ){
        if( st[nod].mn < 0 ) return l;
            else return N;
    }
    int 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) {
    int n = c.size();
    N = n;
    int q = l.size();
    cap = c[0];

    build();

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

        chapeo(1,0,n-1);
    }

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

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