Submission #1208240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208240		tkm_algorithms	Distributing Candies (IOI21_candies)	C++20	100 / 100	1409 ms	43080 KiB

candies

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "candies.h" 
using namespace std;
using ll = long long;
using ull = int64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
//#define ll long long
 
const char nl = '\n';
const ll N = 2e5+1;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 1e9+7;

struct node {
    ll mx, mn, mni, mxi, lz;
    node () {
        mx = -inf, mn = inf, mni = 0, mxi = 0, lz = 0;
    }
};

struct segtree {
    vector<node> tree;
    ll size;
    
    void init(ll n) {
        size = 1;
        while (size < n)size<<=1;
        tree.assign(2*size-1, node());
    }
    
    void build(ll x, ll lx, ll rx) {
        tree[x].mx = tree[x].mn = 0;
        tree[x].mni = tree[x].mxi = lx;
        tree[x].lz = 0;
        
        if (rx-lx==1)return;
        ll mid = lx+rx>>1;
        build(2*x+1, lx, mid);
        build(2*x+2, mid, rx);
        tree[x] = comb(tree[2*x+1], tree[2*x+2]);
    }
    
    void build(ll n) {
        init(n);
        build(0, 0, size);
    }
    
    void addval(ll x, ll v) {
        tree[x].mn += v, tree[x].mx += v;
        tree[x].lz += v;
    }
    
    void push(ll x) {
        tree[2*x+1].mn += tree[x].lz;
        tree[2*x+1].mx += tree[x].lz;
        tree[2*x+2].mn += tree[x].lz;
        tree[2*x+2].mx += tree[x].lz;
        tree[2*x+1].lz += tree[x].lz;
        tree[2*x+2].lz += tree[x].lz;
        tree[x].lz = 0;
    }
    
    node comb(node a, node b) {
        node c;
        if (a.mx > b.mx)c.mx = a.mx, c.mxi = a.mxi;
        else c.mx = b.mx, c.mxi = b.mxi;
        if (a.mn < b.mn)c.mn = a.mn, c.mni = a.mni;
        else c.mn = b.mn, c.mni = b.mni;
        c.lz = 0;
        //c.lz = a.lz+b.lz;
        return c;
    }
    
    void add(ll l, ll r, ll v, ll x, ll lx, ll rx) {
        if (rx <= l || r <= lx)return;
        if (lx >= l && rx <= r) {
            addval(x, v);
            return;
        }
        push(x);
        ll mid = lx+rx>>1;
        add(l, r, v, 2*x+1, lx, mid);
        add(l, r, v, 2*x+2, mid, rx);
        tree[x] = comb(tree[2*x+1], tree[2*x+2]);
    }
    
    void add(ll l, ll r, ll v) {
        add(l, r, v, 0, 0, size);
    }
    
    node get(ll l, ll r, ll x, ll lx, ll rx) {
        if (rx <= l || r <= lx)return node();
        if (lx >= l && rx <= r)return tree[x];
        ll mid = lx+rx>>1;
        push(x);
        return comb(get(l, r, 2*x+1, lx, mid), get(l, r, 2*x+2, mid, rx));
        tree[x] = comb(tree[2*x+1], tree[2*x+2]);
    }
    
    node get(ll l, ll r) {
        return get(l, r, 0, 0, size);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int>r, vector<int> v) {
    segtree st; st.build(sz(l)+1);
    ll n = sz(c), q = sz(l);
    vector<pair<ll, ll>> g[n+1];
    for (ll i = 0; i < q; ++i) {
        g[l[i]].push_back(make_pair(i, v[i]));
        if (r[i] < n-1)g[r[i]+1].push_back(make_pair(i, -v[i]));
    }
    
    vector<int> res(n);
    
    ll sum = 0;
    for (ll i = 0; i < n; ++i) {
        for (auto j: g[i]) {
            st.add(j.first, q, j.second);
            sum += j.second;
        }
        ll id = -1, wall = -1, tp = 0;
        ll lx = 0, rx = q-1;
        while (lx <= rx) {
            ll mid = lx+rx>>1;
            node gt = st.get(mid, q);
            if (gt.mx-gt.mn >= c[i]) {
                lx = mid+1;
                if (gt.mni < gt.mxi)id = gt.mxi, wall = gt.mx, tp = 1;
                else id = gt.mni, wall = gt.mn, tp = 0;
            } else rx = mid-1;
        }
        
        if (id == -1) {
			wall = 0;
            node gt = st.get(0, q);
            if (gt.mn < 0)wall = gt.mn;
            if (gt.mx > 0 && gt.mx >= c[i])wall = gt.mx-c[i];
            res[i] = sum-wall;
            continue;
        }
        
        res[i] = (tp==0?sum-wall:sum-wall+c[i]);
    }
    return res;
}

void solve() {

    ll n, q;
    cin >> n;
    vector<int> c(n);
    for (auto &i : c) cin >> i;
    cin >> q;
    vector<int> l(q), r(q), v(q);
	for (int i = 0; i < q; ++i)cin >> l[i] >> r[i] >> v[i];
    vector<int> result = distribute_candies(c, l, r, v);
    for (const auto &i : result) cout << i << " "; 
}
//int main() {
    //ios::sync_with_stdio(0), cin.tie(0);
    //solve();
//}

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