Submission #1032637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032637		hotboy2703	Distributing Candies (IOI21_candies)	C++17	100 / 100	508 ms	48728 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
namespace trung{
    const ll block = 450;
    const ll MAXN = 2e5+100;
    const ll INF = 1e18;
    pll nxt[MAXN][2];
    struct event{
        ll x,i,v;
    };
    ll m,n;
    namespace segtree{
        struct node{
            pll min1,max1;
        };
        const node worst = {MP(INF,-1),MP(-INF,-1)};
        node tree[MAXN*4];
        ll lazy[MAXN*4];
        void push(ll id,ll v){
            lazy[id]+=v;
            tree[id].min1.fi += v;
            tree[id].max1.fi += v;
        }
        void lz(ll id){
            push(id<<1,lazy[id]);
            push(id<<1|1,lazy[id]);
            lazy[id] = 0;
        }
        node combine(node x,node y){
            node res;
            if (y.min1.fi < x.min1.fi)res.min1=y.min1;
            else res.min1 = x.min1;
            if (y.max1.fi > x.max1.fi)res.max1=y.max1;
            else res.max1 = x.max1;
            return res;
        }
        void build(ll id = 1,ll l = 0,ll r = m){
            tree[id] = {MP(0,l),MP(0,l)};
            if (l < r){
                ll mid = (l + r) >> 1;
                build(id<<1,l,mid);
                build(id<<1|1,mid+1,r);
            }
        }
        void update(ll i,ll v,ll id=1,ll l = 0,ll r = m){
            // cout<<id<<' '<<l<<' '<<r<<endl;
            if (r < i)return;
            if (i <= l){
                push(id,v);
                return;
            }
            lz(id);
            ll mid = (l + r) >> 1;
            update(i,v,id<<1,l,mid);
            update(i,v,id<<1|1,mid+1,r);
            tree[id] = combine(tree[id<<1],tree[id<<1|1]);
        }
        node get(ll l1,ll r1,ll id = 1,ll l = 0,ll r = m){
            if (l > r1 || l1 > r)return worst;
            if (l1 <= l && r <= r1){
                return tree[id];
            }
            lz(id);
            ll mid = (l + r) >> 1;
            return combine(get(l1,r1,id<<1,l,mid),get(l1,r1,id<<1|1,mid+1,r));
        }
    }
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    using namespace trung;
    n = c.size();
    m = sz(l);
    vector <event> all;
    for (ll i = 0;i < m;i ++){
        all.push_back({l[i],i+1,v[i]});
        all.push_back({r[i]+1,i+1,-v[i]});
    }
    sort(all.begin(),all.end(),[](event a1,event a2){return a1.x < a2.x;});
    using namespace segtree;
    build();
    vector <int> res(n);
    for (ll i = 0,ptr = 0;i < n;i ++){
        while (ptr < sz(all) && all[ptr].x == i){
            update(all[ptr].i,all[ptr].v);
            ptr++;
        }
        pll cur = get(0,m).min1;
        ll state = 0;
        while (cur.se < m){
            // cout<<cur.fi<<' '<<cur.se<<endl;
            pll tmp;
            if (state == 0){
                tmp = get(cur.se+1,m).max1;
            }
            else tmp = get(cur.se+1,m).min1;
            if (abs(cur.fi-tmp.fi) <= c[i])break;
            cur = tmp;
            state = 1-state;
        }
        res[i] = get(m,m).min1.fi - cur.fi + (state ? c[i] : 0);
    }
    return res;
}

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