oj.uz

Submission #533115

# Submission time Handle Problem Language Result Execution time Memory
533115 2022-03-04T21:16:12 Z VodkaInTheJar Distributing Candies (IOI21_candies) C++17
30 / 100
 5000 ms 39896 KB 
#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

const int maxn = 2e5 + 3;

struct node {
    int min_val, max_val, max_cap, min_cap;
    int lazy_add_val, lazy_set_val, lazy_add_cap, lazy_set_cap;
    node() {lazy_add_val = lazy_add_cap = 0, lazy_set_val = lazy_set_cap = -1;}
};

node tr[maxn * 4];
void merge(int v) {
    tr[v].min_val = min(tr[v * 2].min_val, tr[v * 2 + 1].min_val);
    tr[v].max_val = max(tr[v * 2].max_val, tr[v * 2 + 1].max_val);
    tr[v].min_cap = min(tr[v * 2].min_cap, tr[v * 2 + 1].min_cap);
    tr[v].max_cap = max(tr[v * 2].max_cap, tr[v * 2 + 1].max_cap);
}

int arr[maxn];
void build(int v, int l, int r) {
    if (l == r) {
        tr[v].min_val = tr[v].max_val = 0;
        tr[v].min_cap = tr[v].max_cap = arr[l];

        return;
    }

    int mid = (l + r) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);

    merge(v);
}

void push(int v, int l, int r) {
    if (tr[v].lazy_set_val != -1) {
        tr[v].min_val = tr[v].max_val = tr[v].lazy_set_val;
        if (l != r) {
            tr[v * 2].lazy_set_val = tr[v * 2 + 1].lazy_set_val = tr[v].lazy_set_val;
            tr[v * 2].lazy_add_val = tr[v * 2 + 1].lazy_add_val = 0;
        }
    }

    tr[v].min_val += tr[v].lazy_add_val, tr[v].max_val += tr[v].lazy_add_val;
    if (l != r)
        tr[v * 2].lazy_add_val += tr[v].lazy_add_val, tr[v * 2 + 1].lazy_add_val += tr[v].lazy_add_val;

    if (tr[v].lazy_set_cap != -1) {
        tr[v].min_cap = tr[v].max_cap = tr[v].lazy_set_cap;
        if (l != r) {
            tr[v * 2].lazy_set_cap = tr[v * 2 + 1].lazy_set_cap = tr[v].lazy_set_cap;
            tr[v * 2].lazy_add_cap = tr[v * 2 + 1].lazy_add_cap = 0;
        }
    }

    tr[v].min_cap += tr[v].lazy_add_cap, tr[v].max_cap += tr[v].lazy_add_cap;
    if (l != r)
        tr[v * 2].lazy_add_cap += tr[v].lazy_add_cap, tr[v * 2 + 1].lazy_add_cap += tr[v].lazy_add_cap;

    tr[v].lazy_add_cap = tr[v].lazy_add_val = 0;
    tr[v].lazy_set_cap = tr[v].lazy_set_val = -1;
}

void add_range(int v, int l, int r, int ll, int rr, int x) {
    push(v, l, r);
    if (l > rr || r < ll)
        return;

    int mid = (l + r) / 2;
    if (l >= ll && r <= rr) {
        if (tr[v].min_cap >= x) {
            tr[v].lazy_add_val += x;
            tr[v].lazy_add_cap -= x;
            push(v, l, r);

            return;
        }

        if (tr[v].max_cap < x) {
            if (tr[v].min_cap == tr[v].max_cap) {
                tr[v].lazy_add_val += tr[v].min_cap;
                tr[v].lazy_set_cap = 0;
                push(v, l, r);

                return;
            }
        }
    }

    add_range(v * 2, l, mid, ll, rr, x);
    add_range(v * 2 + 1, mid + 1, r, ll, rr, x);

    merge(v);
}

void sub_range(int v, int l, int r, int ll, int rr, int x) {
    push(v, l, r);
    if (l > rr || r < ll)
        return;

    int mid = (l + r) / 2;
    if (l >= ll && r <= rr) {
        if (tr[v].min_val >= x) {
            tr[v].lazy_add_val -= x;
            tr[v].lazy_add_cap += x;
            push(v, l, r);

            return;
        }

        if (tr[v].max_val < x) {
            if (tr[v].min_val == tr[v].max_val) {
                tr[v].lazy_add_cap += tr[v].min_val;
                tr[v].lazy_set_val = 0;
                push(v, l, r);

                return;
            }
        }
    }

    sub_range(v * 2, l, mid, ll, rr, x);
    sub_range(v * 2 + 1, mid + 1, r, ll, rr, x);

    merge(v);
}

int get(int v, int l, int r, int pos) {
    push(v, l, r);
    if (l == r)
        return tr[v].min_val;

    int mid = (l + r) / 2;
    if (pos <= mid)
        return get(v * 2, l, mid, pos);

    else
        return get(v * 2 + 1, mid + 1, r, pos);
}

vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v) {
    int n = (int)c.size();
    for (int i = 1; i <= n; i++)
        arr[i] = c[i-1];

    build(1, 1, n);

    int q = (int)l.size();
    for (int i = 0; i < q; i++) {
        if (v[i] > 0)
            add_range(1, 1, n, l[i] + 1, r[i] + 1, v[i]);

        else
            sub_range(1, 1, n, l[i] + 1, r[i] + 1, -v[i]);
    }

    vector <int> ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = get(1, 1, n, i + 1);

    return ans;
}

/*
int main() {
    int n, q;
    cin >> n >> q;
    vector <int> c(n), l(q), r(q), v(q);
    for (int i = 0; i < n; i++)
        cin >> c[i];

    for (int i = 0; i < q; i++)
        cin >> l[i] >> r[i] >> v[i];

    auto ans = distribute_candies(c, l, r, v);
    for (auto i: ans)
        cout << i << " ";
    cout << endl;
}

 */

/*
3 2
10 15 13
0 2 20
0 1 -11
 */

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25344 KB Output is correct
2 Correct 10 ms 25352 KB Output is correct
3 Correct 11 ms 25292 KB Output is correct
4 Correct 12 ms 25368 KB Output is correct
5 Correct 45 ms 25448 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 37172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25292 KB Output is correct
2 Correct 167 ms 32996 KB Output is correct
3 Correct 95 ms 31724 KB Output is correct
4 Correct 384 ms 39040 KB Output is correct
5 Correct 491 ms 39492 KB Output is correct
6 Correct 631 ms 39896 KB Output is correct
7 Correct 516 ms 39180 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25332 KB Output is correct
2 Correct 10 ms 25292 KB Output is correct
3 Execution timed out 5050 ms 32600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25344 KB Output is correct
2 Correct 10 ms 25352 KB Output is correct
3 Correct 11 ms 25292 KB Output is correct
4 Correct 12 ms 25368 KB Output is correct
5 Correct 45 ms 25448 KB Output is correct
6 Execution timed out 5036 ms 37172 KB Time limit exceeded
7 Halted 0 ms 0 KB -