Submission #1229305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229305		mariaclara	Distributing Candies (IOI21_candies)	C++17	100 / 100	515 ms	42796 KiB

candies

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll INF = 1e15;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

struct no{
    ll mi = INF, ma = -INF;
    int ind_mi = -1, ind_ma = -1;
};

no operator + (no A, no B) {
    no C;
    C.mi = min(A.mi, B.mi);
    C.ma = max(A.ma, B.ma);

    if(A.mi < B.mi) C.ind_mi = A.ind_mi;
    else if(A.mi > B.mi) C.ind_mi = B.ind_mi;
    else C.ind_mi = max(A.ind_mi, B.ind_mi);

    if(A.ma < B.ma) C.ind_ma = B.ind_ma;
    else if(A.ma > B.ma) C.ind_ma = A.ind_ma;
    else C.ind_ma = max(A.ind_ma, B.ind_ma);

    return C;
}

vl lazy;
vector<no> seg;

void build(int node, int l, int r) {
    if(l == r) {
        seg[node].mi = seg[node].ma = 0;
        seg[node].ind_mi = seg[node].ind_ma = l;
        return;
    }

    int mid = (l+r)/2;

    build(2*node, l, mid);
    build(2*node+1, mid+1, r);

    seg[node] = seg[2*node] + seg[2*node+1];
}

void prop(int node, int l, int r) {
    seg[node].mi += lazy[node];
    seg[node].ma += lazy[node];

    if(l != r) {
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
    }

    lazy[node] = 0;
}

void update(int node, int l, int r, int p, int q, int val) {
    prop(node, l, r);

    if(r < p or q < l) return;
    if(p <= l and r <= q) {
        lazy[node] = val;
        prop(node, l, r);
        return;
    }

    int mid = (l+r)/2;
    update(2*node, l, mid, p, q, val);
    update(2*node+1, mid+1, r, p, q, val);
    seg[node] = seg[2*node] + seg[2*node+1];
}

no query(int node, int l, int r, int c, no at) {
    prop(node, l, r);

    if(l == r) return seg[node] + at;

    int mid = (l+r)/2;

    prop(2*node+1, mid+1, r);
    no suf = seg[2*node+1] + at;

    if(suf.ma - suf.mi > c) return query(2*node+1, mid+1, r, c, at);
    return query(2*node, l, mid, c, suf);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int N = sz(c), Q = sz(l);

    lazy.resize(4*Q+10);
    seg.resize(4*Q+10);

    vector<vi> line(N);

    for(int q = 0; q < Q; q++) {
        line[l[q]].pb(q+1);
        if(r[q]+1 != N) line[r[q]+1].pb(-q-1);
    }

    ll TOT = 0;
    vi ans(N);

    build(1, 0, Q);

    for(int i = 0; i < N; i++) {
        for(auto q : line[i]) {
            if(q > 0) {
                update(1, 0, Q, q, Q, v[q-1]);
                TOT += v[q-1];
            } else {
                update(1, 0, Q, -q, Q, -v[-q-1]);
                TOT -= v[-q-1];
            }
        }

        no at;
        at = query(1, 0, Q, c[i], at);

        if(at.ma - at.mi <= c[i]) ans[i] = max(0LL,TOT-at.mi);
        else if(at.ind_ma >= at.ind_mi) ans[i] = c[i] - at.ma + TOT;
        else ans[i] = TOT - at.mi;
    }

    return ans;
}

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