Submission #1213402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213402		omsincoconut	Distributing Candies (IOI21_candies)	C++17	0 / 100	303 ms	32520 KiB

candies

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

using namespace std;
typedef long long ll;

const int MAXN = 2e5+5, MAXT = 4*MAXN+10;

ll C;

pair<ll, ll> merge(pair<ll, ll> a, pair<ll, ll> b) {
    if (a.second >= b.first) return make_pair(a.first, min(C, a.second-b.first+b.second));
    else return make_pair(a.first-a.second+b.first, min(C, b.second));
}

vector<pair<ll, ll>> tree(MAXT), lazy(MAXT);

void push(int v, int l, int r) {
    tree[v] = merge(tree[v], lazy[v]);
    if (l < r) {
        lazy[v<<1] = merge(lazy[v<<1], lazy[v]);
        lazy[(v<<1)+1] = merge(lazy[(v<<1)+1], lazy[v]);
    }
    lazy[v] = make_pair(0, 0);
}

void update(int l, int r, pair<ll, ll> val, int tl = 0, int tr = MAXN, int v = 1) {
    push(v, tl, tr);
    if (l <= tl && tr <= r) {
        lazy[v] = merge(lazy[v], val);
        push(v, tl, tr);
        return;
    }

    if (l > tr || tl > r) return;
    int mid = (tl+tr)>>1;
    update(l, r, val, tl, mid, v<<1);
    update(l, r, val, mid+1, tr, (v<<1)+1);
    tree[v] = merge(tree[v<<1], tree[(v<<1)+1]);
}

pair<ll, ll> query(int x, int tl = 0, int tr = MAXN, int v = 1) {
    push(v, tl, tr);
    if (tl == tr) return tree[v];
    int mid = (tl+tr)>>1;
    if (x <= mid) return query(x, tl, mid, v<<1);
    else return query(x, mid+1, tr, (v<<1)+1);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    C = c[0];

    for (int i = 0; i < q; i++) {
        v[i] = min((ll)v[i], C);
        if (v[i] > 0) update(l[i], r[i], {0LL, (ll)v[i]});
        else update(l[i], r[i], {-(ll)v[i], 0LL});
    }

    vector<int> s(n);
    for (int i = 0; i < n; i++) s[i] = query(i).second;
    return s;
}

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