oj.uz

Submission #435006

# Submission time Handle Problem Language Result Execution time Memory
435006 2021-06-22T19:12:48 Z Hegdahl Distributing Candies (IOI21_candies) C++17
0 / 100
 146 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 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 = 1e9, min_up = 1e9;
        max_down = 0, max_up = 0;

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

        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 = 1e9;
                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 = -1e9;
                return;
            }

            lazy -= x;
            recalc();
        }

    }

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

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

        /*
        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.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 146 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 -