제출 #1203875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203875		badge881	Distributing Candies (IOI21_candies)	C++20	100 / 100	651 ms	58068 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

const int MxN = 2e5 + 5;
int n, q;
long long lazy[MxN * 4];
const long long Inf = 1e18;

// every segments are [a;b]
// tree store with root at 0 and left child at i*2+1 and right child at i*2+2

struct node
{
    long long val;
    pair<long long, long long> mx, mn;
    node() : val(0), mx({0, -1}), mn({0, -1}) {}
    node(long long val, long long idx) : val(val), mx({val, idx}), mn({val, idx}) {}
    node(long long mx, long long mn, long long idx) : val(0), mx({mx, idx}), mn({mn, idx}) {}
    friend node operator+(const node &l, const node &r)
    {
        node res = node();
        res.val = l.val + r.val;
        res.mx = max(l.mx, r.mx);
        res.mn = min(l.mn, r.mn);
        return res;
    }
} tree[MxN * 4];

pair<node, long long> operator+(pair<node, long long> c, node o)
{
    c.first = c.first + o;
    return c;
}

void push(long long l, long long r, long long idx)
{
    tree[idx].val += lazy[idx];
    tree[idx].mx.first += lazy[idx];
    tree[idx].mn.first += lazy[idx];
    if (l < r)
    {
        lazy[idx * 2 + 1] += lazy[idx];
        lazy[idx * 2 + 2] += lazy[idx];
    }
    lazy[idx] = 0;
}

void build(long long l, long long r, long long idx)
{
    if (l == r)
        return void(tree[idx] = node(0, l));
    long long mid = (l + r) >> 1LL;
    build(l, mid, idx * 2 + 1);
    build(mid + 1, r, idx * 2 + 2);
    tree[idx] = tree[idx * 2 + 1] + tree[idx * 2 + 2];
}

void update(long long l, long long r, long long idx, long long tl, long long tr, long long val)
{
    push(l, r, idx);
    if (l > tr || r < tl)
        return;
    if (l >= tl && r <= tr)
    {
        lazy[idx] += val;
        push(l, r, idx);
        return;
    }
    long long mid = (l + r) >> 1LL;
    push(l, mid, idx * 2 + 1);
    push(mid + 1, r, idx * 2 + 2);
    update(l, mid, idx * 2 + 1, tl, tr, val);
    update(mid + 1, r, idx * 2 + 2, tl, tr, val);
    tree[idx] = tree[idx * 2 + 1] + tree[idx * 2 + 2];
}

pair<node, long long> query(long long l, long long r, long long idx, long long k, node cur)
{
    push(l, r, idx);
    if (l == r)
        return {tree[idx] + cur, l};
    long long mid = (l + r) >> 1LL;
    push(l, mid, idx * 2 + 1);
    push(mid + 1, r, idx * 2 + 2);
    node qrr = tree[idx * 2 + 2] + cur;
    if (qrr.mx.first - qrr.mn.first > k)
        return query(mid + 1, r, idx * 2 + 2, k, cur);
    else
        return query(l, mid, idx * 2 + 1, k, qrr);
}

node oo(long long l, long long r, long long idx, long long pos)
{
    push(l, r, idx);
    if (l == r)
        return tree[idx];
    long long mid = (l + r) >> 1LL;
    push(l, mid, idx * 2 + 1);
    push(mid + 1, r, idx * 2 + 2);
    if (pos <= mid)
        return oo(l, mid, idx * 2 + 1, pos);
    else
        return oo(mid + 1, r, idx * 2 + 2, pos);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    n = c.size();
    q = l.size();
    vector<int> s(n);
    vector<vector<pair<long long, long long>>> cq(n, vector<pair<long long, long long>>());
    for (int i = 0; i < q; i++)
    {
        cq[l[i]].emplace_back(v[i], i);
        if (r[i] + 1 < n)
            cq[r[i] + 1].emplace_back(-v[i], i);
    }
    build(0, q - 1 + 2, 0);
    long long cur = 0;
    update(0, q - 1 + 2, 0, 0, q - 1 + 2, Inf);
    update(0, q - 1 + 2, 0, 1, q - 1 + 2, -Inf);
    for (int i = 0; i < n; i++)
    {
        for (auto &[x, y] : cq[i])
            update(0, q - 1 + 2, 0, y + 2, q - 1 + 2, x), cur += x;
        auto cqr = query(0, q - 1 + 2, 0, c[i], node(-Inf, Inf, 0));
        auto z = cqr.first;
        if (z.mx.second < z.mn.second)
            s[i] = cur - z.mn.first;
        else
            s[i] = cur - (z.mx.first - c[i]);
    }
    return s;
}

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