Submission #949751

#	Time	Username	Problem	Language	Result	Execution time	Memory
949751		Nhoksocqt1	Distributing Candies (IOI21_candies)	C++17	30 / 100	837 ms	33320 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];

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 Node {
    int sl, sr, v;

    Node(int _l = 0, int _r = 0, int _v = 0) : sl(_l), sr(_r), v(_v) {};
};

const int BLOCK = 450;

vector<ii> B[MAXN];
Node node[MAXN], nodeBlock[450];
int L[450], R[450], bel[MAXN], cNow, numBlock;

inline void mergeNode(Node &a, const Node &b) {
    if(a.sr + a.v < b.sl) {
        a.v = b.sl - a.sr;
    } else
        if(a.sl + a.v > b.sr) {
            a.v = b.sr - a.sl;
        }


    a.sl += a.v, a.sr += a.v;
    a.sl = max(a.sl, b.sl), a.sr = min(a.sr, b.sr);
    a.sl -= a.v, a.sr -= a.v;
    a.v += b.v;
}

void build(void) {
    numBlock = (numQuery + BLOCK - 1) / BLOCK;
    for (int i = 0; i < numBlock; ++i) {
        L[i] = i * BLOCK + 1;
        R[i] = min(numQuery, (i + 1) * BLOCK);

        nodeBlock[i] = Node(0, cNow, 0);
        for (int j = L[i]; j <= R[i]; ++j) {
            node[j] = Node(0, cNow, 0);
            bel[j] = i;
        }
    }
}

void update(int i, int v, bool isAdded) {
    if(isAdded) {
        node[i] = Node(max(0, -v), min(cNow, cNow - v), v);
    } else {
        node[i] = Node(0, cNow, 0);
    }

    nodeBlock[bel[i]] = Node(0, cNow, 0);
    for (int j = L[bel[i]]; j <= R[bel[i]]; ++j)
        mergeNode(nodeBlock[bel[i]], node[j]);
}

Node query(void) {
    Node res = Node(0, cNow, 0);
    for (int i = 0; i < numBlock; ++i)
        mergeNode(res, nodeBlock[i]);

    return res;
}

void sub3(void) {
    cNow = capa[1];
    for (int t = 1; t <= numQuery; ++t) {
        int l(qr[t].l), r(qr[t].r), v(qr[t].v);
        v = ((v > 0) - (v < 0)) * min(abs(v), cNow);
        B[l].push_back({t, v});
        B[r + 1].push_back({-t, v});
    }

    build();
    for (int i = 1; i <= nArr; ++i) {
        for (int it = 0; it < sz(B[i]); ++it) {
            int u(B[i][it].fi), v(B[i][it].se);
            update(abs(u), v, (u > 0));
        }

        Node res = query();
        //assert(result[i] == res.sl + res.v);
        //if(result[i] != res.sl + res.v) exit(1);
        result[i] = res.sl + res.v;
    }
}

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
        if(*min_element(capa + 1, capa + nArr + 1) == *max_element(capa + 1, capa + nArr + 1)) {
            sub3();
        }

    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] = (i == 0) ? Random(100, 100) : C[0]; 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(-1e2, 1e2); 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: 27 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33