oj.uz

Submission #435037

# Submission time Handle Problem Language Result Execution time Memory
435037 2021-06-22T20:46:48 Z VEGAnn Distributing Candies (IOI21_candies) C++17
100 / 100
 3008 ms 41852 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define l2 array<ll,2>
#define sz(x) ((int)x.size())
#define PB push_back
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 200100;
const ll OO = 1e18;
int n, q;
vector<i2> events[N];
ll psh[4 * N];
l2 mn[N * 4], mx[N * 4];

void pull(int v){
    mn[v] = min(mn[v + v], mn[v + v + 1]);
    mx[v] = max(mx[v + v], mx[v + v + 1]);
}

void build(int v, int l, int r){
    psh[v] = 0;

    if (l == r){
        mn[v] = {0, -l};
        mx[v] = {0, l};
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    pull(v);
}

void push(int v){
    if (psh[v] != 0){
        mn[v][0] += psh[v];
        mx[v][0] += psh[v];

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[v + v + 1] += psh[v];
        }

        psh[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, ll vl){
    push(v);

    if (l > r) return;

    if (tl == l && tr == r){
        psh[v] += vl;

        push(v);

        return;
    }

    int md = (tl + tr) >> 1;

    update(v + v, tl, md, l, min(r, md), vl);
    update(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    pull(v);
}

l2 get_max(int v, int tl, int tr, int l, int r){
    push(v);

    if (l > r) return {-OO, -1};

    if (tl == l && tr == r) return mx[v];

    int md = (tl + tr) >> 1;

    return max(get_max(v + v, tl, md, l, min(r, md)),
               get_max(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

l2 get_min(int v, int tl, int tr, int l, int r){
    push(v);

    if (l > r) return {+OO, -1};

    if (tl == l && tr == r) return mn[v];

    int md = (tl + tr) >> 1;

    return min(get_min(v + v, tl, md, l, min(r, md)),
               get_min(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = sz(c);
    q = sz(l);

    for (int i = 0; i < q; i++){
        events[l[i]].PB({i, +v[i]});
        events[r[i] + 1].PB({i, -v[i]});
    }

    build(1, 0, q);

    vector<int> a;

    a.resize(n);

    for (int i = 0; i < n; i++){
        for (i2 cr : events[i])
            update(1, 0, q, cr[0] + 1, q, cr[1]);

        if (mx[1][0] - mn[1][0] <= c[i]){
            if (mn[1][0] < 0){
                a[i] = get_max(1, 0, q, q, q)[0] - mn[1][0];
            } else {
                a[i] = get_max(1, 0, q, q, q)[0];
            }
        } else {
            int lf = 0, rt = q;

            while (lf < rt){
                int md = (lf + rt + 1) >> 1;

                l2 fi = get_max(1, 0, q, md, q);
                l2 se = get_min(1, 0, q, md, q);

                if (fi[0] - se[0] > c[i])
                    lf = md;
                else rt = md - 1;
            }

            l2 fi = get_max(1, 0, q, lf, q);
            l2 se = get_min(1, 0, q, lf, q);

            if (-fi[1] < se[1]){
                a[i] = ll(c[i]) - (fi[0] - get_max(1, 0, q, q, q)[0]);
            } else {
                a[i] = get_max(1, 0, q, q, q)[0] - se[0];
            }
        }
    }

    return a;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 7 ms 5324 KB Output is correct
5 Correct 15 ms 5324 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2873 ms 41772 KB Output is correct
2 Correct 2915 ms 41768 KB Output is correct
3 Correct 2582 ms 41852 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 506 ms 36872 KB Output is correct
3 Correct 813 ms 8864 KB Output is correct
4 Correct 3008 ms 41768 KB Output is correct
5 Correct 3001 ms 41772 KB Output is correct
6 Correct 2843 ms 41776 KB Output is correct
7 Correct 2727 ms 41780 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 178 ms 35676 KB Output is correct
4 Correct 641 ms 7776 KB Output is correct
5 Correct 1641 ms 37884 KB Output is correct
6 Correct 1892 ms 37884 KB Output is correct
7 Correct 2211 ms 37884 KB Output is correct
8 Correct 1559 ms 37884 KB Output is correct
9 Correct 2201 ms 37920 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 7 ms 5324 KB Output is correct
5 Correct 15 ms 5324 KB Output is correct
6 Correct 2873 ms 41772 KB Output is correct
7 Correct 2915 ms 41768 KB Output is correct
8 Correct 2582 ms 41852 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 506 ms 36872 KB Output is correct
11 Correct 813 ms 8864 KB Output is correct
12 Correct 3008 ms 41768 KB Output is correct
13 Correct 3001 ms 41772 KB Output is correct
14 Correct 2843 ms 41776 KB Output is correct
15 Correct 2727 ms 41780 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 178 ms 35676 KB Output is correct
19 Correct 641 ms 7776 KB Output is correct
20 Correct 1641 ms 37884 KB Output is correct
21 Correct 1892 ms 37884 KB Output is correct
22 Correct 2211 ms 37884 KB Output is correct
23 Correct 1559 ms 37884 KB Output is correct
24 Correct 2201 ms 37920 KB Output is correct
25 Correct 4 ms 4940 KB Output is correct
26 Correct 484 ms 7728 KB Output is correct
27 Correct 457 ms 36808 KB Output is correct
28 Correct 1991 ms 41740 KB Output is correct
29 Correct 2570 ms 41772 KB Output is correct
30 Correct 2758 ms 41760 KB Output is correct
31 Correct 2866 ms 41768 KB Output is correct
32 Correct 2785 ms 41756 KB Output is correct