oj.uz

Submission #1062981

# Submission time Handle Problem Language Result Execution time Memory
1062981 2024-08-17T12:55:16 Z j_vdd16 Distributing Candies (IOI21_candies) C++17
100 / 100
 2276 ms 58556 KB 
#include "candies.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define ll long long
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef tuple<ll, pair<ll, int>, pair<ll, int>> Entry;

struct SegTree {
    int n = -1, N = -1;
    vector<Entry> tree; //sum, min, max
    vector<ll> lazy;
    Entry id = { 0, {LLONG_MAX / 2, 0}, {LLONG_MIN / 2, 0}};

    SegTree(int _n) {
        n = _n;
        N = 1;
        while (N < n) N *= 2;

        tree.resize(2 * N);
        loop(i, n) {
            tree[N + i] = { 0, { 0, i}, { 0, i }};
        }
        for (int i = N - 1; i >= 1; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }

        lazy.resize(2 * N, 0);
        //sums = SumTree(n);
    }

    Entry merge(Entry a, Entry b) {
        auto [s1, min1, max1] = a;
        auto [s2, min2, max2] = b;

        ll s = s1 + s2;
        ii mn;
        if (min1.first < min2.first) {
            mn.first = min1.first;
            mn.second = min1.second;
        }
        else {
            mn.first = min2.first;
            mn.second = min2.second;
        }

        ii mx;
        if (max1.first > max2.first) {
            mx.first = max1.first;
            mx.second = max1.second;
        }
        else {
            mx.first = max2.first;
            mx.second = max2.second;
        }

        return {s, mn, mx};
    }

    void add2(int idx, ll v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;
 
        if (tr - tl == 1) {
            get<0>(tree[i]) += v;
            return;
        }
 
        int tm = (tl + tr) / 2;
        if (idx < tm) {
            add2(idx, v, 2 * i, tl, tm);
        }
        else {
            add2(idx, v, 2 * i + 1, tm, tr);
        }
 
        get<0>(tree[i]) = get<0>(tree[2 * i]) + get<0>(tree[2 * i + 1]);
    }
    void add(int l, int r, ll v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;

        if (lazy[i]) {
            get<1>(tree[i]).first += lazy[i];
            get<2>(tree[i]).first += lazy[i];

            if (tr - tl > 1) {
                lazy[2 * i] += lazy[i];
                lazy[2 * i + 1] += lazy[i];
            }
            lazy[i] = 0;
        }

        if (l >= tr || r <= tl) {
            return;
        }
        if (tl >= l && tr <= r) {
            get<1>(tree[i]).first += v;
            get<2>(tree[i]).first += v;

            if (tr - tl > 1) {
                lazy[2 * i] += v;
                lazy[2 * i + 1] += v;
            }

            return;
        }

        int tm = (tl + tr) / 2;
        if (l < tm) {
            add(l, r, v, 2 * i, tl, tm);
            add(l, r, v, 2 * i + 1, tm, tr);
        }
        else {
            add(l, r, 0, 2 * i, tl, tm);
            add(l, r, v, 2 * i + 1, tm, tr);
        }

        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
    
    void set(int idx, const Entry& v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;

        if (tr - tl == 1) {
            tree[i] = v;
            return;
        }

        int tm = (tl + tr) / 2;
        if (idx < tm) {
            set(idx, v, 2 * i, tl, tm);
        }
        else {
            set(idx, v, 2 * i + 1, tm, tr);
        }

        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }

    Entry getRange(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;

        if (lazy[i]) {
            get<1>(tree[i]).first += lazy[i];
            get<2>(tree[i]).first += lazy[i];

            if (tr - tl > 1) {
                lazy[2 * i] += lazy[i];
                lazy[2 * i + 1] += lazy[i];
            }
            lazy[i] = 0;
        }

        if (l >= tr || r <= tl)
            return id;

        if (tl >= l && tr <= r)
            return tree[i];

        int tm = (tl + tr) / 2;
        return merge(getRange(l, r, 2 * i, tl, tm), getRange(l, r, 2 * i + 1, tm, tr));
    }
};

vector<signed> distribute_candies(vector<signed> c, vector<signed> ls, vector<signed> rs, vector<signed> vs) {
    int n = c.size();
    int q = ls.size();

    SegTree segTree(q + 1);
    vvii queryStarts(n), queryEnds(n);
    loop(i, q) {
        int l = ls[i];
        int r = rs[i];
        int v = vs[i];

        queryStarts[l].push_back({v, i + 1});
        queryEnds[r].push_back({v, i + 1});
    }

    vector<signed> s(n);
    loop(i, n) {
        for (auto [v, idx] : queryStarts[i]) {
            segTree.add(idx, q + 1, v);
            segTree.add2(idx, v);
        }
        segTree.set(0, {0, {0, 0}, {c[i], 0}});

        int l = 0, r = q;
        while (l < r) {
            int m = (l + r + 1) / 2;

            //ll diff = sufMax[m].first - sufMin[m].first;
            auto [sum, mn, mx] = segTree.getRange(m, q + 1);

            ll diff = mx.first - mn.first;
            if (diff < (ll)c[i]) {
                r = m - 1;
            }
            else { 
                l = m;
            }
        }

        auto [sum, mn, mx] = segTree.getRange(l, q + 1);
        if (l == 0 && mx.first - mn.first <= (ll)c[i]) {
            //s[i] = cumul.back();
            ll extra = get<0>(segTree.getRange(0, q + 1));
            s[i] = extra;
        }
        else {
            //int lastMin = sufMin[l].second;
            //int lastMax = sufMax[l].second;
            int lastMin = mn.second;
            int lastMax = mx.second;

            ll value = 0;
            if (lastMin >= lastMax) {
                l = lastMin;
            }
            else {
                l = lastMax;
                value = c[i];
            }

            //s[i] += cumul.back() - cumul[l];
            ll extra = get<0>(segTree.getRange(l + 1, q + 1));
            s[i] = value + extra;
        }

        for (auto [v, idx] : queryEnds[i]) {
            segTree.add(idx, q + 1, -v);
            segTree.add2(idx, -v);
        }
    }

    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 8 ms 860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2050 ms 51984 KB Output is correct
2 Correct 2058 ms 55900 KB Output is correct
3 Correct 2033 ms 55900 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 378 ms 42152 KB Output is correct
3 Correct 660 ms 14676 KB Output is correct
4 Correct 2276 ms 57904 KB Output is correct
5 Correct 2257 ms 58192 KB Output is correct
6 Correct 1848 ms 58556 KB Output is correct
7 Correct 1864 ms 58044 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 239 ms 37836 KB Output is correct
4 Correct 550 ms 13136 KB Output is correct
5 Correct 1739 ms 49836 KB Output is correct
6 Correct 1584 ms 49884 KB Output is correct
7 Correct 1505 ms 50352 KB Output is correct
8 Correct 1694 ms 49840 KB Output is correct
9 Correct 1809 ms 50608 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 8 ms 860 KB Output is correct
6 Correct 2050 ms 51984 KB Output is correct
7 Correct 2058 ms 55900 KB Output is correct
8 Correct 2033 ms 55900 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 378 ms 42152 KB Output is correct
11 Correct 660 ms 14676 KB Output is correct
12 Correct 2276 ms 57904 KB Output is correct
13 Correct 2257 ms 58192 KB Output is correct
14 Correct 1848 ms 58556 KB Output is correct
15 Correct 1864 ms 58044 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 239 ms 37836 KB Output is correct
19 Correct 550 ms 13136 KB Output is correct
20 Correct 1739 ms 49836 KB Output is correct
21 Correct 1584 ms 49884 KB Output is correct
22 Correct 1505 ms 50352 KB Output is correct
23 Correct 1694 ms 49840 KB Output is correct
24 Correct 1809 ms 50608 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 590 ms 13852 KB Output is correct
27 Correct 361 ms 43096 KB Output is correct
28 Correct 1981 ms 56504 KB Output is correct
29 Correct 1910 ms 56916 KB Output is correct
30 Correct 1981 ms 56916 KB Output is correct
31 Correct 1911 ms 57168 KB Output is correct
32 Correct 1897 ms 57528 KB Output is correct