oj.uz

Submission #435003

# Submission time Handle Problem Language Result Execution time Memory
435003 2021-06-22T18:59:35 Z Hegdahl Distributing Candies (IOI21_candies) C++17
0 / 100
 187 ms 20036 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 ms 20036 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -