Submission #951182

#	Time	Username	Problem	Language	Result	Execution time	Memory
951182		Nhoksocqt1	Distributing Candies (IOI21_candies)	C++17	3 / 100	286 ms	40564 KiB

candies

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;

struct Query {
    int l, r, v;
} qr[MAXN];

vector<ii> B[MAXN];
int result[MAXN];
int capa[MAXN], nArr, numQuery;

void sub1(void) {
    for (int i = 1; i <= nArr; ++i)
        result[i] = 0;

    for (int t = 1; t <= numQuery; ++t) {
        int l(qr[t].l), r(qr[t].r), v(qr[t].v);
        for (int i = l; i <= r; ++i)
            result[i] = min(capa[i], max(0, result[i] + v));
    }
}

struct SegNode {
    ll minv, maxv, sumAdd, lz;
} seg[4 * MAXN];

void pushDown(int id) {
    ll &lz(seg[id].lz);

    id <<= 1;
    seg[id] = {seg[id].minv + lz, seg[id].maxv + lz, seg[id].sumAdd + lz, seg[id].lz + lz};
    seg[id | 1] = {seg[id | 1].minv + lz, seg[id | 1].maxv + lz, seg[id | 1].sumAdd + lz, seg[id | 1].lz + lz};
    lz = 0;
}

ll sumAll(0);
void update(int id, int l, int r, int u, int v, int k) {
    seg[id].sumAdd += k;
    if(u <= l && r <= v) {
        seg[id] = {seg[id].minv + k, seg[id].maxv + k, seg[id].sumAdd, seg[id].lz + k};
        return;
    }

    if(seg[id].lz)
        pushDown(id);

    int mid = (l + r) >> 1;
    if(mid >= u)
        update(id << 1, l, mid, u, v, k);

    if(mid + 1 <= v)
        update(id << 1 | 1, mid + 1, r, u, v, k);

    seg[id].minv = min(seg[id << 1].minv, seg[id << 1 | 1].minv);
    seg[id].maxv = max(seg[id << 1].maxv, seg[id << 1 | 1].maxv);
}

int query(int capa) {
    ll minNow(1e18), maxNow(-1e18);
    int id(1), l(1), r(numQuery);
    while(l < r) {
        int mid = (l + r) >> 1;
        if(seg[id].lz)
            pushDown(id);

        id <<= 1;
        if(max(maxNow, seg[id | 1].maxv) - min(minNow, seg[id | 1].minv) > capa) {
            l = mid + 1;
            id |= 1;
        } else {
            maxNow = max(maxNow, seg[id | 1].maxv);
            minNow = min(minNow, seg[id | 1].minv);
            r = mid;
        }
    }

    maxNow = max(maxNow, seg[id].maxv);
    minNow = min(minNow, seg[id].minv);
    if(seg[id].minv < sumAll) {
        return capa - (maxNow - sumAll);
    } else {
        return sumAll - minNow;
    }
}

void magicFunc(void) {
    for (int t = 1; t <= numQuery; ++t) {
        int l(qr[t].l), r(qr[t].r), v(qr[t].v);
        B[l].push_back(ii(t, v));
        B[r + 1].push_back(ii(t, -v));
    }

    for (int i = 1; i <= nArr; ++i) {
        for (int it = 0; it < sz(B[i]); ++it) {
            int j(B[i][it].fi), v(B[i][it].se);
            update(1, 1, numQuery, j, numQuery, v);
            sumAll += v;
        }

        /*cout << result[i] << ' ' << query(capa[i]) << '\n';
        if(query(capa[i]) != result[i])
            exit(1);*/

        result[i] = query(capa[i]);
    }
}

vector<int> distribute_candies(vector<int> _C, vector<int> _L, vector<int> _R, vector<int> _V) {
    nArr = sz(_C);
    for (int i = 1; i <= nArr; ++i)
        capa[i] = _C[i - 1];

    numQuery = sz(_L);
    for (int t = 1; t <= numQuery; ++t)
        qr[t] = {_L[t - 1] + 1, _R[t - 1] + 1, _V[t - 1]};

    if(max(nArr, numQuery) <= 2000) {
        sub1();
    } else {
        magicFunc();
    }

    vector<int> ans;
    for (int i = 1; i <= nArr; ++i)
        ans.push_back(result[i]);

    return ans;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "candies"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> C, L, R, V;
    int N, Q;
    cin >> N >> Q;

    C.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
        C[i] = Random(100, 1e5); cout << C[i] << " \n"[i + 1 == N];
    }

    L.resize(Q), R.resize(Q), V.resize(Q);
    for (int t = 0; t < Q; ++t) {
        cin >> L[t] >> R[t] >> V[t];
        L[t] = Random(0, N - 1), R[t] = Random(L[t], N - 1), V[t] = Random(-1e5, 1e5); cout << L[t] << ' ' << R[t] << ' ' << V[t] << '\n';
    }

    vector<int> ans = distribute_candies(C, L, R, V);
    cout << "ANSWER: ";
    for (int it = 0; it < sz(ans); ++it)
        cout << ans[it] << ' '; cout << '\n';

    return 0;
}

#endif // Nhoksocqt1

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