제출 #435003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435003		Hegdahl	사탕 분배 (IOI21_candies)	C++17	0 / 100	187 ms	20036 KiB

candies

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

#define ar array

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 all_up, all_down;

    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;

        all_up = 0;
        all_down = 1;

        lazy = 0;
    }

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

        all_up = 1;
        all_down = 1;

        for (int i = 0; i < n; ++i) {
            values[i] = max(0, 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]);

            if (values[i] != 0) all_down = 0;
            if (values[i] != positions[i][1]) all_up = 0;
        }

        lazy = 0;
    }

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

        if (x > 0) {
            if (all_up) return;

            if (x <= min_up) {
                min_down += x;
                min_up -= x;
                max_down += x;
                max_up -= x;
                lazy += x;
                all_down = 0;
                return;
            }

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

                min_up = 0;
                min_down = min_cap;

                lazy = 0;
                all_up = 1;
            }

            lazy += x;
            recalc();

        } else {
            if (all_down) return;

            x = -x;

            if (x <= min_down) {
                min_down -= x;
                min_up += x;
                max_down -= x;
                max_up += x;
                lazy -= x;
                all_up = 0;
            }

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

                min_up = min_cap;
                min_down = 0;

                lazy = 0;
                all_down = 1;
            }

            lazy -= x;
            recalc();
        }
    }
};

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);

    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]);
    }

    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