제출 #812239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
812239		penguinman	사탕 분배 (IOI21_candies)	C++17	100 / 100	298 ms	43612 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 segment_tree{
    ll N;
    ll log;
    vi sum, max, min;
    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);
    }
    void update(ll idx, ll val){
        idx += N;
        sum[idx] += val;
        max[idx] = min[idx] = sum[idx];
        idx >>= 1;
        while(idx){
            sum[idx] = sum[idx*2]+sum[idx*2+1];
            max[idx] = std::max(max[idx*2],sum[idx*2]+max[idx*2+1]); 
            min[idx] = std::min(min[idx*2],sum[idx*2]+min[idx*2+1]); 
            idx >>= 1;
        }
    }

    std::tuple<ll,ll,ll,ll> min_right(ll val, std::tuple<ll,ll,ll> state, ll now = 1, ll l = 0, ll r = -1){
        if(r == -1) r = N;
        ll s,ma,mi;
        std::tie(s,ma,mi) = state;
        if(std::max(ma,s+max[now])-std::min(mi,s+min[now]) < val){
            return mtp(r, s+sum[now], std::max(ma,s+max[now]), std::min(mi,s+min[now]));
        }
        if(now >= N) return mtp(l, s+sum[now], std::max(ma,s+max[now]), std::min(mi,s+min[now]));
        ll left,sl,mal,mil;
        std::tie(left,sl,mal,mil) = min_right(val, state, now*2, l, (l+r)/2);
        if(left == (l+r)/2) return min_right(val, mtp(sl, mal, mil), now*2+1, (l+r)/2, r);
        return mtp(left, sl, mal, mil);
    }
};
 
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();
    vii add(N+1), dec(N+1);
    reverse(all(l));
    reverse(all(r));
    reverse(all(v));
    rep(i,0,Q){
        add[l[i]].pb(i);
        dec[r[i]+1].pb(i);
    }
    segment_tree seg(Q);
    vector<int> ans(N);
    rep(i,0,N){
        for(auto j: add[i]) seg.update(j, v[j]);
        for(auto j: dec[i]) seg.update(j, -v[j]);
        ll idx, sum, max, min;
        std::tie(idx, sum, max, min) = seg.min_right(c[i], mtp(0,0,0));
        if(idx >= Q) ans[i] = max;
        else if(v[idx] > 0){
            ans[i] = c[i]+min;
        }
        else{
            ans[i] = max;
        }
    }
    return ans;
}

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