oj.uz

Submission #636711

# Submission time Handle Problem Language Result Execution time Memory
636711 2022-08-30T00:32:04 Z imeimi2000 Distributing Candies (IOI21_candies) C++17
0 / 100
 566 ms 35296 KB 
#include "candies.h"

#include <cstdio>
#include <vector>

using namespace std;

int n, q;
int mx[1 << 19], mn[1 << 19], add[1 << 19];

void lazy(int i) {
    mn[i + i] += add[i];
    mn[i + i + 1] += add[i];
    mx[i + i] += add[i];
    mx[i + i + 1] += add[i];
    add[i + i] += add[i];
    add[i + i + 1] += add[i];
    add[i] = 0;
}

void update(int i, int s, int e, int x, int v) {
    if (e < x) return;
    if (x <= s) {
        mn[i] += v;
        mx[i] += v;
        add[i] += v;
        return;
    }
    lazy(i);
    int m = (s + e) / 2;
    update(i + i, s, m, x, v);
    update(i + i + 1, m + 1, e, x, v);
    mn[i] = min(mn[i + i], mn[i + i + 1]);
    mx[i] = max(mx[i + i], mx[i + i + 1]);
}

int find(int i, int s, int e, int low, int high, int c) {
    if (max(high, mx[i]) - min(low, mn[i]) <= c) return -1;
    if (s == e) return s;
    lazy(i);
    int m = (s + e) / 2;
    int r = find(i + i + 1, m + 1, e, low, high, c);
    if (r != -1) return r;
    return find(i + i, s, m, min(low, mn[i + i + 1]), max(high, mx[i + i + 1]), c);
}

int get(int i, int s, int e, int x) {
    if (s == e) return add[i];
    lazy(i);
    int m = (s + e) / 2;
    if (x <= m) return get(i + i, s, m, x);
    else return get(i + i + 1, m + 1, e, x);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size();
    q = v.size();
    vector<vector<int>> A(n), R(n);
    for (int i = 0; i < q; ++i) {
        A[l[i]].push_back(i);
        R[r[i]].push_back(i);
    }
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        for (int j : A[i]) update(1, 0, q, j + 1, v[j]);
        int x = find(1, 0, q, 1e9, 0, c[i]);
        if (x == -1) ans.push_back(get(1, 0, q, q));
        else {
            int d = get(1, 0, q, q) - get(1, 0, q, x + 1);
            if (v[x] > 0) ans.push_back(c[i] + d);
            else ans.push_back(d);
        }
        for (int j : R[i]) update(1, 0, q, j + 1, -v[j]);
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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