Submission #435012

#	Time	Username	Problem	Language	Result	Execution time	Memory
435012		Hegdahl	Distributing Candies (IOI21_candies)	C++17	0 / 100	153 ms	25236 KiB

candies

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

#define ar array
#define int long long

using namespace std;

struct Bucket {
    vector<ar<int, 2>> positions; 
    vector<int> values;

    int n;

    int min_up, min_down, max_up, max_down, max_cap, min_cap;

    int lazy;

    void init() {
        n = (int)positions.size();
        sort(positions.begin(), positions.end());

        values.resize(n);

        min_down = max_down = 0;
        min_up = 1e9, max_up = 0;
        for (int i = 0; i < n; ++i) {
            min_up = min(min_up, positions[i][1]);
            max_up = max(max_up, positions[i][1]);
        }

        min_cap = min_up;
        max_cap = max_up;

        lazy = 0;
    }

    void recalc() {
        min_down = 1e18, min_up = 1e18;
        max_down = 0, max_up = 0;

        for (int i = 0; i < n; ++i) {
            values[i] = max(0LL, min(positions[i][1], values[i]+lazy));

            min_down = min(min_down, values[i]);
            min_up = min(min_up, positions[i][1]-values[i]);
            max_down = max(max_down, values[i]);
            max_up = max(max_up, positions[i][1]-values[i]);
        }

        lazy = 0;
    }

    void upd(int i, int j, int x) {
        assert(i <= positions[0][0] && j >= positions.back()[0]);

        if (x > 0) {
            if (max_up == 0) return;

            if (x <= min_up) {
                if (min_down == 0) recalc();

                min_down += x;
                min_up -= x;
                max_down += x;
                max_up -= x;
                lazy += x;
                return;
            }

            if (x >= max_up) {
                max_up = 0;
                max_down = max_cap;

                min_up = 0;
                min_down = min_cap;

                lazy = 1e18;
                return;
            }

            lazy += x;
            recalc();

        } else {
            if (max_down == 0) return;

            x = -x;

            if (x <= min_down) {
                if (min_up == 0) recalc();

                min_down -= x;
                min_up += x;
                max_down -= x;
                max_up += x;
                lazy -= x;
                return;
            }

            if (x >= max_down) {
                max_up = max_cap;
                max_down = 0;

                min_up = min_cap;
                min_down = 0;

                lazy = -1e18;
                return;
            }

            lazy -= x;
            recalc();
        }

    }

    void dbg() {
        cerr << min_down << ' ' << max_down << '\n';
        cerr << min_up << ' ' << max_up << '\n';
        cerr << lazy << "\n\n";
    }
};

#undef int
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = (int)c.size();
    int q = (int)v.size();

    const int R = sqrt(n);
    cerr << R << '\n';

    vector<Bucket> buckets((n+R-1)/R);
    vector<int> idxs(n);
    iota(idxs.begin(), idxs.end(), 0);
    sort(idxs.begin(), idxs.end(), [&](int i, int j) {
        return c[i] < c[j];
    });

    for (int i = 0; i < n; ++i)
        buckets[i/R].positions.push_back({idxs[i], c[idxs[i]]});

    for (auto &bucket : buckets)
        bucket.init();

    for (int qq = 0; qq < q; ++qq) {
        for (auto &bucket : buckets)
            bucket.upd(l[qq], r[qq], v[qq]);

        /*
        for (auto &bucket : buckets)
            bucket.dbg(); // */
    }

    vector<int> s(n);

    for (auto &bucket : buckets) {
        bucket.recalc();
        for (int i = 0; i < bucket.n; ++i)
            s[bucket.positions[i][0]] = bucket.values[i];
    }

    return s;
}

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