oj.uz

Submission #1063437

# Submission time Handle Problem Language Result Execution time Memory
1063437 2024-08-17T18:32:19 Z phoenix Distributing Candies (IOI21_candies) C++17
32 / 100
 1349 ms 47700 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;
const int N = (1 << 18);

ll up[2 * N];
pair<ll, int> mn[2 * N];
pair<ll, int> mx[2 * N];

void init() {
    for (int i = 2 * N - 1; i >= 1; i--) {
        if (i >= N) 
            mn[i].second = mx[i].second = i - N;
        else 
            mn[i].second = mx[i].second = mn[2 * i].second;
        mn[i].first = mx[i].first = 0;
    }
}

void setpush(int v, int d) {
    up[v] += d;
    mn[v].first += d;
    mx[v].first += d;
}

void push(int v) {
    if (v >= N || !up[v]) return;
    setpush(2 * v, up[v]);
    setpush(2 * v + 1, up[v]);
    up[v] = 0;
}

void update(int ql, int qr, int d, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return;
    if (ql <= l && r <= qr) {
        setpush(v, d);
        return;
    }
    int mid = (l + r) / 2;
    push(v);
    update(ql, qr, d, l, mid, 2 * v);
    update(ql, qr, d, mid + 1, r, 2 * v + 1);
    mn[v] = min(mn[2 * v], mn[2 * v + 1]);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}

int get(int pos, int l = 0, int r = N - 1, int v = 1) {
    if (l == r)
        return mn[v].first;
    int mid = (l + r) / 2;
    push(v);
    if (pos <= mid) 
        return get(pos, l, mid, 2 * v);
    return get(pos, mid + 1, r, 2 * v + 1);
}
pair<ll, int> get_min(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return {INF, 0};
    if (ql <= l && r <= qr)
        return mn[v];
    int mid = (l + r) / 2;
    push(v);
    return min(get_min(ql, qr, l, mid, 2 * v), 
               get_min(ql, qr, mid + 1, r, 2 * v + 1));
}
pair<ll, int> get_max(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return {-INF, 0};
    if (ql <= l && r <= qr)
        return mx[v];
    int mid = (l + r) / 2;
    push(v);
    return max(get_max(ql, qr, l, mid, 2 * v), 
               get_max(ql, qr, mid + 1, r, 2 * v + 1));
}

int calc(int c) {
    int l = 0, r = N - 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (get_max(mid, N - 1).first - get_min(mid, N - 1).first >= c)
            l = mid;
        else 
            r = mid;
    }
    // cout << c << ":\n";
    // cout << get_min(l, N - 1).first << ' ';
    // cout << get_max(l, N - 1).first << '\n';
    // cout << '\n';
    if (get_min(l, N - 1).second < get_max(l, N - 1).second) {
        return get(N - 1) - get_max(l, N - 1).first + c;
    } else {
        return get(N - 1) - get_min(l, N - 1).first;
    }
}

vector<pair<ll, int>> upd[N];

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    init();
    update(0, 0, +INF);
    int n = c.size(), q = l.size();
    for (int i = 0; i < q; i++) {
        upd[l[i]].push_back({v[i], i + 2});
        upd[r[i]+1].push_back({-v[i], i + 2});
    }
    vector<int> s(n);
    for (int i = 0; i < n; i++) {
        for (auto [v, p] : upd[i]) 
            update(p, N - 1, v);
        s[i] = calc(c[i]);    
    }

    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22872 KB Output is correct
2 Correct 9 ms 23128 KB Output is correct
3 Correct 10 ms 23420 KB Output is correct
4 Correct 11 ms 23340 KB Output is correct
5 Correct 23 ms 23452 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23132 KB Output is correct
2 Incorrect 215 ms 42632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23132 KB Output is correct
2 Correct 14 ms 23132 KB Output is correct
3 Correct 97 ms 39496 KB Output is correct
4 Correct 922 ms 26828 KB Output is correct
5 Correct 1028 ms 42412 KB Output is correct
6 Correct 1016 ms 43184 KB Output is correct
7 Correct 958 ms 43432 KB Output is correct
8 Correct 987 ms 42652 KB Output is correct
9 Correct 1074 ms 43580 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22872 KB Output is correct
2 Correct 9 ms 23128 KB Output is correct
3 Correct 10 ms 23420 KB Output is correct
4 Correct 11 ms 23340 KB Output is correct
5 Correct 23 ms 23452 KB Output is correct
6 Incorrect 1349 ms 47700 KB Output isn't correct
7 Halted 0 ms 0 KB -