Submission #814190

#	Time	Username	Problem	Language	Result	Execution time	Memory
814190		LittleCube	Distributing Candies (IOI21_candies)	C++17	27 / 100	418 ms	49560 KiB

candies

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

struct node
{
    // domain [l, r] -> [l + d, r + d] is linear
    ll l, r, d;
    ll operator()(ll x)
    {
        if (x < l)
            return l + d;
        if (x <= r)
            return x + d;
        return r + d;
    }
} seg[800005];

node merge(node p, node q)
{
    auto [l, r, d] = p;
    auto [x, y, _] = q;

    // merge domain
    l += d, r += d;
    l = max(l, x);
    r = min(r, y);
    if (l > r)
        l = r = d;
    l -= d, r -= d;

    // compute d
    d = q(p(l)) - l;
    return node{l, r, d};
}

int n, q;
node emp;

void init()
{
    for (int i = 1; i <= 4 * q; i++)
        seg[i] = emp;
}

void modify(int pos, node val, int i = 1, int L = 0, int R = q - 1)
{
    if (L == R)
        seg[i] = val;
    else
    {
        int mid = (L + R) / 2;
        if (pos <= mid)
            modify(pos, val, i << 1, L, mid);
        else
            modify(pos, val, i << 1 | 1, mid + 1, R);
        seg[i] = merge(seg[i << 1], seg[i << 1 | 1]);
    }
}

vector<int> in[200000], out[200001];
node base[200000];
vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v)
{
    vector<int> ans;
    n = c.size(), q = l.size();
    int C = c[0];
    emp = {0, C, 0};
    for (int i = 0; i < q; i++)
    {
        in[l[i]].emplace_back(i);
        out[r[i] + 1].emplace_back(i);
        base[i] = emp;
        if (v[i] < 0)
        {
            v[i] = max(-C, v[i]);
            base[i] = node{-v[i], C, v[i]};
        }
        else
        {
            v[i] = min(C, v[i]);
            base[i] = node{0, C - v[i], v[i]};
        }
    }
    init();
    for (int i = 0; i < n; i++)
    {
        for (auto j : in[i])
            modify(j, base[j]);
        for (auto j : out[i])
            modify(j, emp);
        ans.emplace_back(seg[1](0));
    }
    return ans;
}

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