oj.uz

Submission #624301

# Submission time Handle Problem Language Result Execution time Memory
624301 2022-08-07T17:47:17 Z Jomnoi Distributing Candies (IOI21_candies) C++17
100 / 100
 1849 ms 43192 KB 
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;

const int MAX_N = 2e5 + 5;
const int MAX_Q = 2e5 + 5;
const long long INF = 1e18 + 7;

int N, Q;
vector <int> S;
vector <pair <int, int>> queries[MAX_N];

struct Node {
    long long mn, mx;

    Node() : mn(0), mx(0) {}
    Node(long long n, long long x) : mn(n), mx(x) {}

    Node operator+(const Node &o) const {
        return Node(min(mn, o.mn), max(mx, o.mx));
    }
}tree[4 * MAX_Q];
long long lazy[4 * MAX_Q];

void push(int idx, int l, int r) {
    if(lazy[idx] != 0) {
        tree[idx].mn += lazy[idx];
        tree[idx].mx += lazy[idx];
        if(l != r) {
            lazy[idx * 2] += lazy[idx];
            lazy[idx * 2 + 1] += lazy[idx];
        }
        lazy[idx] = 0;
    }
}

void update(int idx, int l, int r, int ql, int qr, long long v) {
    push(idx, l, r);
    if(r < ql or qr < l) {
        return;
    }
    if(ql <= l and r <= qr) {
        lazy[idx] += v;
        push(idx, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(idx * 2, l, mid, ql, qr, v);
    update(idx * 2 + 1, mid + 1, r, ql, qr, v);
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

long long getMin(int idx, int l, int r, int lb) {
    push(idx, l, r);
    if(r < lb) {
        return INF;
    }
    if(lb <= l) {
        return tree[idx].mn;
    }

    int mid = (l + r) / 2;
    return min(getMin(idx * 2, l, mid, lb), getMin(idx * 2 + 1, mid + 1, r, lb));
}

long long getMax(int idx, int l, int r, int lb) {
    push(idx, l, r);
    if(r < lb) {
        return -INF;
    }
    if(lb <= l) {
        return tree[idx].mx;
    }

    int mid = (l + r) / 2;
    return max(getMax(idx * 2, l, mid, lb), getMax(idx * 2 + 1, mid + 1, r, lb));
}

long long getPos(int idx, int l, int r, int q) {
    push(idx, l, r);
    if(l == r) {
        return tree[idx].mx;
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        return getPos(idx * 2, l, mid, q);
    }
    return getPos(idx * 2 + 1, mid + 1, r, q);
}

vector <int> distribute_candies(vector <int> C, vector <int> L, vector <int> R, vector <int> V) {
    N = C.size(), Q = L.size();
    for(int i = 0; i < Q; i++) {
        queries[L[i]].emplace_back(i + 1, V[i]);
        queries[R[i] + 1].emplace_back(i + 1, -V[i]);
    }

    S.resize(N);
    for(int i = 0; i < N; i++) {
        for(auto [q, v] : queries[i]) {
            update(1, 0, Q, q, Q, v);
        }

        if(getMax(1, 0, Q, 0) - getMin(1, 0, Q, 0) < C[i]) {
            S[i] = getMax(1, 0, Q, Q) - getMin(1, 0, Q, 0);
            continue;
        }

        int l = 0, r = Q, pos = 0;
        while(l <= r) {
            int mid = (l + r) / 2;

            if(getMax(1, 0, Q, mid) - getMin(1, 0, Q, mid) >= C[i]) {
                l = mid + 1;
                pos = mid;
            }
            else {
                r = mid - 1;
            }
        }

        long long last = getMax(1, 0, Q, Q);
        long long mn = getMin(1, 0, Q, pos), mx = getMax(1, 0, Q, pos);
        if(getPos(1, 0, Q, pos) == mx) {
            S[i] = last - mn;
        }
        else {
            S[i] = C[i] - (mx - last);
        }
    }
    return S;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 11 ms 17432 KB Output is correct
3 Correct 11 ms 17620 KB Output is correct
4 Correct 11 ms 17748 KB Output is correct
5 Correct 17 ms 17788 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1814 ms 36616 KB Output is correct
2 Correct 1719 ms 40556 KB Output is correct
3 Correct 1531 ms 40396 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 288 ms 33832 KB Output is correct
3 Correct 586 ms 24180 KB Output is correct
4 Correct 1849 ms 42416 KB Output is correct
5 Correct 1821 ms 42796 KB Output is correct
6 Correct 1830 ms 43192 KB Output is correct
7 Correct 1826 ms 42540 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17540 KB Output is correct
2 Correct 10 ms 17492 KB Output is correct
3 Correct 157 ms 30128 KB Output is correct
4 Correct 473 ms 21036 KB Output is correct
5 Correct 1157 ms 33412 KB Output is correct
6 Correct 1362 ms 33840 KB Output is correct
7 Correct 1595 ms 33876 KB Output is correct
8 Correct 1060 ms 35380 KB Output is correct
9 Correct 1556 ms 36184 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 11 ms 17432 KB Output is correct
3 Correct 11 ms 17620 KB Output is correct
4 Correct 11 ms 17748 KB Output is correct
5 Correct 17 ms 17788 KB Output is correct
6 Correct 1814 ms 36616 KB Output is correct
7 Correct 1719 ms 40556 KB Output is correct
8 Correct 1531 ms 40396 KB Output is correct
9 Correct 9 ms 17492 KB Output is correct
10 Correct 288 ms 33832 KB Output is correct
11 Correct 586 ms 24180 KB Output is correct
12 Correct 1849 ms 42416 KB Output is correct
13 Correct 1821 ms 42796 KB Output is correct
14 Correct 1830 ms 43192 KB Output is correct
15 Correct 1826 ms 42540 KB Output is correct
16 Correct 8 ms 17540 KB Output is correct
17 Correct 10 ms 17492 KB Output is correct
18 Correct 157 ms 30128 KB Output is correct
19 Correct 473 ms 21036 KB Output is correct
20 Correct 1157 ms 33412 KB Output is correct
21 Correct 1362 ms 33840 KB Output is correct
22 Correct 1595 ms 33876 KB Output is correct
23 Correct 1060 ms 35380 KB Output is correct
24 Correct 1556 ms 36184 KB Output is correct
25 Correct 7 ms 17492 KB Output is correct
26 Correct 342 ms 22068 KB Output is correct
27 Correct 294 ms 33424 KB Output is correct
28 Correct 1240 ms 41052 KB Output is correct
29 Correct 1507 ms 41424 KB Output is correct
30 Correct 1717 ms 41616 KB Output is correct
31 Correct 1794 ms 41816 KB Output is correct
32 Correct 1825 ms 42008 KB Output is correct