oj.uz

Submission #1071886

# Submission time Handle Problem Language Result Execution time Memory
1071886 2024-08-23T12:07:48 Z Boas Distributing Candies (IOI21_candies) C++17
100 / 100
 2211 ms 45360 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int> vi;
typedef signed i32;
typedef vector<i32> vi32;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef set<int> si;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define ALL(x) begin(x), end(x)
#define sz(x) (int)x.size()

class node
{
public:
    int sufMax = 0, sufMin = 0, mxIx = 0, mnIx = 0;
    node operator+(const node &b) const
    {
        node res;
        if (this->sufMax == LLONG_MIN / 2)
            return b;
        if (b.sufMax == LLONG_MIN / 2)
            return *this;
        if (this->sufMin < b.sufMin)
        {
            res.sufMin = this->sufMin;
            res.mnIx = this->mnIx;
        }
        else
        {
            res.sufMin = b.sufMin;
            res.mnIx = b.mnIx;
        }
        if (this->sufMax > b.sufMax)
        {
            res.sufMax = this->sufMax;
            res.mxIx = this->mxIx;
        }
        else
        {
            res.sufMax = b.sufMax;
            res.mxIx = b.mxIx;
        }
        return res;
    }
    node &operator+=(const int &v)
    {
        this->sufMin += v;
        this->sufMax += v;
        return *this;
    }
    bool operator==(const node &b)
    {
        return b.sufMax == this->sufMax &&
               b.sufMin == this->sufMin;
    }
};

node def = {LLONG_MIN / 2, LLONG_MAX / 2, 0, 0}; // default

vector<node> tree;
vi lazy;

int treeSz = 1;

void propagate(int i)
{
    tree[i] += lazy[i];
    if (i < treeSz)
    {
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
    }
    lazy[i] = {};
}

node get(int i, int l, int r, int ql, int qr)
{
    if (qr < l || r < ql)
        return def;
    int m = l + (r - l) / 2;
    propagate(i);
    if (ql <= l && r <= qr)
        return tree[i];
    return get(2 * i, l, m, ql, qr) +
           get(2 * i + 1, m + 1, r, ql, qr);
}

void add(int i, int l, int r, int ql, int qr, int v)
{
    propagate(i);
    if (qr < l || r < ql)
        return;
    int m = l + (r - l) / 2;
    if (ql <= l && r <= qr)
    {
        lazy[i] += v;
        propagate(i);
        return;
    }
    add(2 * i, l, m, ql, qr, v);
    add(2 * i + 1, m + 1, r, ql, qr, v);
    tree[i] = tree[2 * i] + tree[2 * i + 1];
}

vi32 distribute_candies(vi32 c, vi32 l, vi32 r, vi32 v)
{
    int n = sz(c);
    int q = sz(l);
    while (treeSz <= q)
        treeSz *= 2;
    tree.resize(treeSz * 2);
    lazy.resize(treeSz * 2);
    loop(treeSz, i)
    {
        tree[treeSz + i].mxIx = i;
        tree[treeSz + i].mnIx = i;
    }
    for (int i = treeSz - 1; i >= 1; i--)
    {
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    vvi queryBegin(n), queryEnd(n);
    loop(q, i)
    {
        queryBegin[l[i]].pb(i);
        queryEnd[r[i]].pb(i);
    }
    vi32 s(n);
    loop(n, i)
    {
        for (int j : queryBegin[i])
        {
            add(1, 0, treeSz - 1, 0, j, v[j]);
        }
        int lo = 0, hi = q;
        while (hi > lo)
        {
            int m = lo + (hi - lo + 1) / 2;
            node res = get(1, 0, treeSz - 1, m, q);
            int d = res.sufMax - res.sufMin;
            if (d >= c[i])
            {
                lo = m;
            }
            else
                hi = m - 1;
        }
        node res = get(1, 0, treeSz - 1, hi, q);
        int d = res.sufMax - res.sufMin;
        if (d >= c[i])
        {
            if (hi == res.mxIx)
            {
                s[i] = c[i] + (i32)res.sufMin;
            }
            else
            {
                s[i] = (i32)res.sufMax;
            }
        }
        else
        {
            s[i] = (i32)res.sufMax;
        }
        for (int j : queryEnd[i])
        {
            add(1, 0, treeSz - 1, 0, j, -v[j]);
        }
    }
    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 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 11 ms 604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1648 ms 45292 KB Output is correct
2 Correct 1821 ms 45352 KB Output is correct
3 Correct 1910 ms 45140 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 264 ms 31216 KB Output is correct
3 Correct 754 ms 12368 KB Output is correct
4 Correct 2211 ms 45300 KB Output is correct
5 Correct 2023 ms 45340 KB Output is correct
6 Correct 1520 ms 45348 KB Output is correct
7 Correct 1611 ms 45344 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 160 ms 29020 KB Output is correct
4 Correct 577 ms 12376 KB Output is correct
5 Correct 1640 ms 40556 KB Output is correct
6 Correct 1599 ms 40560 KB Output is correct
7 Correct 1344 ms 40556 KB Output is correct
8 Correct 1731 ms 40556 KB Output is correct
9 Correct 2031 ms 40372 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 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 11 ms 604 KB Output is correct
6 Correct 1648 ms 45292 KB Output is correct
7 Correct 1821 ms 45352 KB Output is correct
8 Correct 1910 ms 45140 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 264 ms 31216 KB Output is correct
11 Correct 754 ms 12368 KB Output is correct
12 Correct 2211 ms 45300 KB Output is correct
13 Correct 2023 ms 45340 KB Output is correct
14 Correct 1520 ms 45348 KB Output is correct
15 Correct 1611 ms 45344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 160 ms 29020 KB Output is correct
19 Correct 577 ms 12376 KB Output is correct
20 Correct 1640 ms 40556 KB Output is correct
21 Correct 1599 ms 40560 KB Output is correct
22 Correct 1344 ms 40556 KB Output is correct
23 Correct 1731 ms 40556 KB Output is correct
24 Correct 2031 ms 40372 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 682 ms 12512 KB Output is correct
27 Correct 242 ms 31348 KB Output is correct
28 Correct 1973 ms 45340 KB Output is correct
29 Correct 1793 ms 45288 KB Output is correct
30 Correct 1719 ms 45136 KB Output is correct
31 Correct 1704 ms 45300 KB Output is correct
32 Correct 1568 ms 45360 KB Output is correct