Submission #485309

#	Time	Username	Problem	Language	Result	Execution time	Memory
485309		fcmalkcin	Distributing Candies (IOI21_candies)	C++17	100 / 100	1084 ms	35544 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn = 2e5 + 10;
const ll mod = 998244353 ;
const ll base = 3e18;
struct tk {
    ll pmn = 0, pmx = 0, sum = 0;
    ll chk = 0;
};
tk mer(tk a, tk b) {
    if (a.chk == 0)
        return b;

    if (b.chk == 0)
        return a;

    tk c;
    c.sum = a.sum + b.sum;
    c.pmn = min(a.pmn, a.sum + b.pmn);
    c.pmx = max(a.pmx, a.sum + b.pmx);
    c.chk = a.chk;
    return c;
}
tk st[4 * maxn];
void update(ll id, ll left, ll right, ll x, ll diff) {
    if (x > right || x < left)
        return ;

    if (left == right) {

        st[id].sum += diff;
        st[id].pmn = min(0ll, st[id].sum);
        st[id].pmx = max(0ll, st[id].sum);
        st[id].chk = (st[id].sum >= 0) + 1;
        return ;
    }

    ll mid = (left + right) / 2;
    update(id * 2, left, mid, x, diff);
    update(id * 2 + 1, mid + 1, right, x, diff);
    st[id] = mer(st[id * 2], st[id * 2 + 1]);
}
tk get(ll id, ll left, ll right, ll x, ll y) {
    tk a;

    if (x > right || y < left || x > y)
        return a;

    if (x <= left && y >= right)
        return st[id];

    ll mid = (left + right) / 2;
    return mer(get(id * 2, left, mid, x, y), get(id * 2 + 1, mid + 1, right, x, y));
}
vector<int> adj[maxn];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    ll n = c.size();
    ll q = l.size();

    for (int i = 0; i < q; i++) {
        adj[l[i]].pb(i + 2);

        if (r[i] + 1 < n)
            adj[r[i] + 1].pb(-(i + 2));
    }

    int mx = 0;

    for (int i = 0; i < n; i++)
        mx = max(mx, c[i]);

    update(1, 1, q + 1, 1, -mx);
    vector<int> ans;

    for (int i = 0; i < n; i++) {
        for (auto to : adj[i]) {
            if (to > 0) {
                update(1, 1, q + 1, to, v[to - 2]);
            } else {
                update(1, 1, q + 1, -to, -v[-to - 2]);
            }
        }

        adj[i].clear();
        ll l = 1, h = q + 1;

        while (l <= h) {
            ll mid = (l + h) / 2;
            tk p = get(1, 1, q + 1, mid, q + 1);

            if (p.pmx - p.pmn >= c[i])
                l = mid + 1;
            else
                h = mid - 1;
        }

        tk nw = get(1, 1, q + 1, h, q + 1);
        /*if (i==n-1)
        {
            cout <<h<<" "<<q+2<<endl;
            cout <<nw.sum<<" "<<nw.pmn<<" "<<nw.pmx<<" "<<nw.chk<<endl;
        }*/
        //assert(nw.pmx-nw.pmn>=c[i]);
        ans.pb((nw.chk == 2 ? (int)(c[i] - (nw.pmx - nw.sum)) : (int)(nw.sum - nw.pmn)));
    }

    return ans;
}


/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    vector<int > l;
    vector<int > r;
    vector<int > v;
    vector<int > t;
    ll n;
     cin>> n;
     while (n--)
     {
         int x;
         cin>> x;
         t.pb(x);
     }
    ll q;
     cin>> q;
     while (q--)
     {
         int a, b, c;
         cin>>a>> b>> c;
         l.pb(a);
         r.pb(b);
         v.pb(c);
     }
     vector<int> ans=distribute_candies(t,l,r,v);
     for (auto to:ans) cout <<to<<endl;


}*/

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