Submission #1207800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207800		tkm_algorithms	Distributing Candies (IOI21_candies)	C++20	0 / 100	498 ms	22792 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;

vector<ll> p(N+1);

struct node {
    ll set, sum, lz;
    node() {
        set = -1, sum = 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 apply(ll x, ll v) {
        tree[x].sum = tree[x].set = v;
        tree[x].lz = 0;
    }
    
    void add(ll x, ll v) {
        tree[x].sum += v, tree[x].lz += v;
    }
    
    void push(ll x, ll y, ll lx, ll rx, ll lef) {
        if (tree[x].set != -1) {
            if (tree[x].set == 0)apply(y, tree[x].set);
            else {
                int mid = lx+rx>>1;
                apply(y, (!lef?p[mid]-p[lx]:p[rx]-p[mid]));
            }
            tree[x].set = -1;
        }
        if (tree[x].lz != 0) {
            add(y, tree[x].lz);
            tree[x].lz = 0;
        }
    }
    
    void radd(ll l, ll r, ll v, ll x, ll lx, ll rx) {
        if (rx <= l || r <= lx)return;
        if (lx >= l && rx <= r) {
            add(x, v);
            return;
        }
        node a = tree[x];
        push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
        int mid = lx+rx>>1;
        radd(l, r, v, 2*x+1, lx, mid);
        radd(l, r, v, 2*x+2, mid, rx);
        tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum;
    }
    
    void radd(ll l, ll r, ll v) {
        radd(l, r, v, 0, 0, size);
    }
    
    void set0(ll l, ll r, ll x, ll lx, ll rx) {
        if (rx <= l || r <= lx)return;
        if (lx >= l && rx <= r) {
            apply(x, 0);
            return;
        }
        node a = tree[x];
        push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
        int mid = lx+rx>>1;
        set0(l, r, 2*x+1, lx, mid);
        set0(l, r, 2*x+2, mid, rx);
        tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum;
    }
    
    void set0(ll l, ll r) {
        set0(l, r, 0, 0, size);
    }
    
    void setmx(ll l, ll r, ll x, ll lx, ll rx) {
        if (rx <= l || r <= lx)return;
        if (lx >= l && rx <= r) {
            tree[x].sum = tree[x].set = p[rx]-p[lx];
            //cout << p[rx] << " " << p[lx] << nl;
            tree[x].lz = 0;
            return;
        }
        node a = tree[x];
        push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
        ll mid = lx+rx>>1;
        setmx(l, r, 2*x+1, lx, mid);
        setmx(l, r, 2*x+2, mid, rx);
        tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum;
    }
    
    void setmx(ll l, ll r) {
        setmx(l, r, 0, 0, size);
    }
    
    ll get(ll i, ll x, ll lx, ll rx) {
        if (rx-lx==1)return tree[x].sum;
        ll mid = lx+rx>>1;
        node a = tree[x];
        push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
        if (i < mid)return get(i, 2*x+1, lx, mid);
        else return get(i, 2*x+2, mid, rx);
        tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum;
    }
    
    ll get(ll i) {
        return get(i, 0, 0, size);
    }   
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    ll n = sz(c), q = sz(l);
    
    vector<pair<int, int>> b;
    for (int i = 0; i < n; ++i)b.push_back(make_pair(c[i], i));
    
    sort(all(b));
    sort(all(c));
    
    for (ll i = 1; i <= n; ++i)p[i] = c[i-1]+p[i-1];
    
    segtree st; st.init(n+1);
    for (ll i = 0; i < q; ++i) {
        st.radd(l[i], r[i]+1, v[i]);
        if (v[i] > 0) {
            ll a = st.get(i);
            if (a <= c[0])continue;
            ll lx = 0, rx = n;
            while (rx-lx>1) {
                ll mid = lx+rx>>1;
                if (st.get(mid) <= c[mid])rx = mid;
                else lx = mid;
            }
            //cout << lx+1 << nl;
            st.setmx(0, lx+1);
        } 
        if (v[i] < 0){
            ll a = st.get(i);
            if (a >= 0)continue;
            ll lx = 0, rx = n;
            while (rx-lx>1) {
                ll mid = lx+rx>>1;
                if (st.get(mid) >= 0)rx = mid;
                else lx = mid;
            }
            st.set0(0, lx+1);
        }
    }
    
    vector<int> res(n);
    for (ll i = 0; i < n; ++i)
		res[b[i].second] = st.get(i);
    return res;
}

//int main() {
    //vector<int> ans = distribute_candies({(int)1e5, 15}, {0, 0, 0}, {1, 1, 1}, {(int)1e9, (int)1e9});
    //for (auto &i: ans)cout << i << " ";
    //return 0;
//}

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