oj.uz

Submission #562118

# Submission time Handle Problem Language Result Execution time Memory
562118 2022-05-14T05:43:10 Z kartel Distributing Candies (IOI21_candies) C++17
100 / 100
 1663 ms 74780 KB 
#include <bits/stdc++.h>

//#include "grader.cpp"
#include "candies.h"

#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;

struct node {
    ll mn, mx, D;
    int pos_mn, pos_mx;

    node() {mn = 2e18; mx = -2e18; D = 0;}
    node(ll x, int i) {mn = mx = x; pos_mn = pos_mx = i; D = 0;}

    void mrg(node &l, node &r) {
        if (l.mn < r.mn) {
            mn = l.mn;
            pos_mn = l.pos_mn;
        } else {
            mn = r.mn;
            pos_mn = r.pos_mn;
        }
        if (l.mx > r.mx) {
            mx = l.mx;
            pos_mx = l.pos_mx;
        } else {
            mx = r.mx;
            pos_mx = r.pos_mx;
        }
    }
};

struct seg_tree {
    vector <node> t;
    int n;

    void build(int v, int l, int r) {
        if (l == r) {
            t[v] = node(0, l);
        } else {
            int md = (l + r) >> 1;
            build(v * 2, l, md);
            build(v * 2 + 1, md + 1, r);
            t[v].mrg(t[v * 2], t[v * 2 + 1]);
        }
    }

    seg_tree() {}
    seg_tree(int _n) {
        n = _n;
        t.resize(8 * n);
        build(1, 0, n - 1);
    }

    void push(int v) {
        if (t[v].D) {
            t[v].mn += t[v].D;
            t[v].mx += t[v].D;
            t[v * 2].D += t[v].D;
            t[v * 2 + 1].D += t[v].D;
            t[v].D = 0;
        }
    }

    void upd(int v, int l, int r, int tl, int tr, ll val) {
        push(v);
        if (l > r || tl > tr || tl > r || l > tr) {
            return;
        }
        if (l >= tl && r <= tr) {
            t[v].D += val;
            push(v);
            return;
        }
        int md = (l + r) >> 1;
        upd(v * 2, l, md, tl, tr, val);
        upd(v * 2 + 1, md + 1, r, tl, tr, val);

        t[v].mrg(t[v * 2], t[v * 2 + 1]);
    }

    node get(int v, int l, int r, int tl, int tr) {
        push(v);
        if (l > r || tl > tr || tl > r || l > tr) {
            return node();
        }

        if (l >= tl && r <= tr) {
            return t[v];
        }
        int md = (l + r) >> 1;
        node L = get(v * 2, l, md, tl, tr);
        node R = get(v * 2 + 1, md + 1, r, tl, tr);
        node cur = node();
        cur.mrg(L, R);
        return cur;
    }

    void upd(int l, int r, ll val) {
        upd(1, 0, n - 1, l, r, val);
    }

    node get(int l, int r) {
        return get(1, 0, n - 1, l, r);
    }
};

vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v) {
    int n = sz(c), q = sz(l);
    vector <vector <int> > add(n + 1), del(n + 1);

    for (int i = 0; i < q; i++) {
        add[l[i]].pb(i + 1);
        del[r[i] + 1].pb(i + 1);
    }

    seg_tree t(q + 1);
    vector <int> ans;
    for (int i = 0; i < n; i++) {
        for (auto &id : add[i]) {
            t.upd(id, q, v[id - 1]);
        }
        for (auto &id : del[i]) {
            t.upd(id, q, -v[id - 1]);
        }

        int l = 0;
        int r = q;
        while (l < r) {
            int md = (l + r + 1) >> 1;
            node cur = t.get(md, q);

            if (cur.mx - cur.mn >= c[i]) {
                l = md;
            } else {
                r = md - 1;
            }
        }

        int suf = r;
        node sf = t.get(suf, q);
        if (sf.mx - sf.mn < c[i]) {
            ans.pb(t.get(q, q).mx - sf.mn);
            continue;
        }
        int pos_mn = sf.pos_mn;
        int pos_mx = sf.pos_mx;

        if (pos_mx >= pos_mn) {
            ll val = t.get(q, q).mx;
            ans.pb(val - sf.mx + c[i]);
        } else {
            ans.pb(t.get(q, q).mx - sf.mn);
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 7 ms 980 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 74452 KB Output is correct
2 Correct 1663 ms 74380 KB Output is correct
3 Correct 1595 ms 74356 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 303 ms 58052 KB Output is correct
3 Correct 384 ms 12992 KB Output is correct
4 Correct 1604 ms 74384 KB Output is correct
5 Correct 1612 ms 74404 KB Output is correct
6 Correct 1569 ms 74296 KB Output is correct
7 Correct 1580 ms 74416 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 133 ms 56912 KB Output is correct
4 Correct 375 ms 12956 KB Output is correct
5 Correct 1042 ms 69204 KB Output is correct
6 Correct 1113 ms 69164 KB Output is correct
7 Correct 1069 ms 69356 KB Output is correct
8 Correct 1060 ms 69164 KB Output is correct
9 Correct 1039 ms 69164 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 1577 ms 74452 KB Output is correct
7 Correct 1663 ms 74380 KB Output is correct
8 Correct 1595 ms 74356 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 303 ms 58052 KB Output is correct
11 Correct 384 ms 12992 KB Output is correct
12 Correct 1604 ms 74384 KB Output is correct
13 Correct 1612 ms 74404 KB Output is correct
14 Correct 1569 ms 74296 KB Output is correct
15 Correct 1580 ms 74416 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 133 ms 56912 KB Output is correct
19 Correct 375 ms 12956 KB Output is correct
20 Correct 1042 ms 69204 KB Output is correct
21 Correct 1113 ms 69164 KB Output is correct
22 Correct 1069 ms 69356 KB Output is correct
23 Correct 1060 ms 69164 KB Output is correct
24 Correct 1039 ms 69164 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 379 ms 13064 KB Output is correct
27 Correct 327 ms 58188 KB Output is correct
28 Correct 1641 ms 74368 KB Output is correct
29 Correct 1608 ms 74708 KB Output is correct
30 Correct 1552 ms 74424 KB Output is correct
31 Correct 1481 ms 74372 KB Output is correct
32 Correct 1506 ms 74780 KB Output is correct