Submission #811297

#	Time	Username	Problem	Language	Result	Execution time	Memory
811297		penguinman	Distributing Candies (IOI21_candies)	C++17	40 / 100	5021 ms	57144 KiB

candies

#include "candies.h"
 
#include <bits/stdc++.h>
 
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;
 
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
 
struct lazy_segment_tree{
    ll N;
    ll log;
    vi sum, max, min;
    vi lsum, lmax, lmin;
    lazy_segment_tree(ll n){
        N = 1;
        log = 0;
        while(N <= n){
            N *= 2;
            log++;
        }
        sum.resize(2*N);
        max.resize(2*N); 
        min.resize(2*N);
        lsum.resize(2*N);
        lmax.resize(2*N);
        lmin.resize(2*N);
    }
    void update(ll a, ll b, ll val){
        ll l = a+N, r = b+N-1;
        per(i,log,0){
            eval(l>>i);
            eval(r>>i);
        }
        while(l < r){
            if(l & 1){
                lmax[l] = std::max(lmax[l], lsum[l]+val);
                lmin[l] = std::min(lmin[l], lsum[l]+val);
                lsum[l] += val;
                l++;
            }
            l >>= 1;
            if((r&1) == 0){
                lmax[r] = std::max(lmax[r], lsum[r]+val);
                lmin[r] = std::min(lmin[r], lsum[r]+val);
                lsum[r] += val;
                r--;
            }
            r >>= 1;
        }
        if(l == r){
            lmax[l] = std::max(lmax[l], lsum[l]+val);
            lmin[l] = std::min(lmin[l], lsum[l]+val);
            lsum[l] += val;
        }
    }
    /*void update(ll a, ll b, ll val, ll now = 1, ll l = 0, ll r = -1){
        if(r == -1) r = N;
        if(r <= a || b <= l) return;
        eval(now);
        if(a <= l && r <= b){
            if(val > 0) lmax[now] = val;
            else lmin[now] = val;
            lsum[now] += val;
            return;
        }
        update(a,b,val,now*2,l,(l+r)/2);
        update(a,b,val,now*2+1,(l+r)/2,r);
    }*/
    pii calc(ll now){
        now += N;
        per(i,log,0){
            eval(now>>i);
        }
        return mp(max[now], min[now]);
    }
    void eval(ll now){
        if(lmax[now]){
            max[now] = std::max(max[now], sum[now]+lmax[now]);
            if(now < N){
                lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
                lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
            }
            lmax[now] = 0;
        }
        if(lmin[now]){
            min[now] = std::min(min[now], sum[now]+lmin[now]);
            if(now < N){
                lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
                lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
            }
            lmin[now] = 0;
        }
        if(lsum[now]){
            sum[now] += lsum[now];
            if(now < N){
                lsum[now*2] += lsum[now];
                lsum[now*2+1] += lsum[now];
            }
            lsum[now] = 0;
        }
        lmax[now] = lmin[now] = lsum[now] = 0;
    }
};
 
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();
    ll Q = l.size();
    vi left(N,-1), right(N,Q);
    while(true){
        lazy_segment_tree seg(N);
        vi mid(N);
        bool flg = true;
        vii query(Q+1);
        rep(i,0,N){
            if(left[i]+1 < right[i]){
                mid[i] = (left[i]+right[i])/2;
                query[mid[i]].pb(i);
                flg = false;
            }
        }
        if(flg) break;
        per(i,Q,0){
            if(i < Q){
                seg.update(l[i], r[i]+1, v[i]);
            }
            for(auto el: query[i]){
                auto ret = seg.calc(el);
                if(c[el] <= ret.first-ret.second) left[el] = mid[el];
                else right[el] = mid[el];
            }
        }
    }
    vector<int> ans(N);
    {
        vii max(Q+1), min(Q+1);
        rep(i,0,N){
            if(left[i] == -1) max[0].pb(i);
            else{
                if(v[left[i]] > 0){
                    min[left[i]].pb(i);
                }
                else{
                    max[left[i]].pb(i);
                }
            }
        }
        lazy_segment_tree seg(N);
        per(i,Q,0){
            if(i < Q){
                seg.update(l[i], r[i]+1, v[i]);
            }
            for(auto el: max[i]){
                ans[el] = seg.calc(el).first;
            }
            for(auto el: min[i]){
                ans[el] = c[el]+seg.calc(el).second;
            }
        }
    }
    return ans;
}

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