Submission #614058

#	Time	Username	Problem	Language	Result	Execution time	Memory
614058		hibiki	Distributing Candies (IOI21_candies)	C++17	0 / 100	403 ms	46684 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
typedef pair<int, int> pii;

int n, q;
vector<int> c, l, r, v, ans;
vector<pii> po_up[200005];

struct node
{
    long long mx = 0, mn = 0;
    long long lazy = 0;
    node *l = NULL, *r = NULL;
} * root;

void unlazy(node *ptr)
{
    if (ptr->l && ptr->r)
    {
        ptr->l->lazy += ptr->lazy;
        ptr->r->lazy += ptr->lazy;
        ptr->lazy = 0;
    }
}

node *build(int l, int r)
{
    node *ptr = new node;
    if (l == r)
        return ptr;
    int mid = (l + r) >> 1;
    ptr->l = build(l, mid);
    ptr->r = build(mid + 1, r);
    return ptr;
}

void up(node *ptr, int l, int r, int po, long long val)
{
    if (po <= l)
    {
        ptr->lazy += val;
        return;
    }
    if (r < po)
        return;
    int mid = (l + r) >> 1;
    up(ptr->l, l, mid, po, val);
    up(ptr->r, mid + 1, r, po, val);
    ptr->mx = max(ptr->l->mx + ptr->l->lazy, ptr->r->mx + ptr->r->lazy);
    ptr->mn = min(ptr->l->mn + ptr->l->lazy, ptr->r->mn + ptr->r->lazy);
    return;
}

long long sum = 0, mx = -1e18, mn = 1e18;
long long que(node *ptr, int l, int r, int lim)
{
    if (l == r)
    {
        if (ptr->mn + ptr->lazy < sum)
            return sum + lim - mx;
        else
            return sum - mn;
    }
    unlazy(ptr);
    int mid = (l + r) >> 1;
    if (max(mx, ptr->r->mx + ptr->r->lazy) - min(mn, ptr->r->mn + ptr->r->lazy) > lim)
        return que(ptr->r, mid + 1, r, lim);
    else
    {
        mx = max(mx, ptr->r->mx + ptr->r->lazy);
        mn = min(mn, ptr->r->mn + ptr->r->lazy);
        return que(ptr->l, l, mid, lim);
    }
}

vector<int> distribute_candies(vector<int> C, vector<int> L,
                               vector<int> R, vector<int> V)
{
    n = sz(C), q = sz(L);
    c = C, l = L, r = R, v = V;
    root = build(0, q);

    for (int i = 0; i < q; i++)
    {
        po_up[l[i]].pb({i + 1, v[i]});
        po_up[r[i] + 1].pb({i + 1, -v[i]});
    }

    for (int i = 0; i < n; i++)
    {
        mx = -1e18, mn = 1e18;
        for (auto val : po_up[i])
            up(root, 0, q, val.f, val.s), sum += val.s;

        if (root->mx - root->mn <= c[i])
            ans.pb(sum - root->mn);
        else
            ans.pb(que(root, 0, q, c[i]));
    }
    return ans;
}

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