Submission #1032678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032678		hotboy2703	Distributing Candies (IOI21_candies)	C++17	8 / 100	353 ms	43352 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));
        }
        node get_last(ll c,node suf = worst,ll id = 1,ll l = 0,ll r = m){
            node sus = combine(suf,tree[id]);
            if (sus.max1.fi - sus.min1.fi <= c)return sus;
            if (l==r){
                return sus;
            }
            lz(id);
            ll mid = (l + r) >> 1;
            node res = get_last(c,suf,id<<1|1,mid+1,r);
            if (res.max1.fi - res.min1.fi <= c)res = get_last(c,res,id<<1,l,mid);
            return res;
        }
    }
}
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++;
        }
        node tmp = get_last(c[i]);
        // cout<<tmp.max1.fi<<' '<<tmp.max1.se<<' '<<tmp.min1.fi<<' '<<tmp.min1.se<<' '<<get(m,m)endl;
        if (tmp.max1.fi - tmp.min1.fi <= c[i]){
            res[i] = get(m,m).max1.fi;
        }
        else if (tmp.min1.se > tmp.max1.se){
            res[i] = get(m,m).max1.fi - tmp.min1.fi;
        }
        else{
            res[i] = get(m,m).max1.fi - tmp.max1.fi + c[i];
        }
    }
    return res;
}

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