oj.uz

Submission #1071843

# Submission time Handle Problem Language Result Execution time Memory
1071843 2024-08-23T11:49:08 Z Boas Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 29012 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()

// en de segment tree bevat een suffix sum, suffix max en suffix min over de queries
class node
{
public:
    int sufMax = 0, sufMin = 0, mxIx = 0, mnIx = 0, diff = 0;
    node operator+(const node &b) const
    {
        node res;
        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;
    }
};

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

vector<node> tree;
vi lazy;
vi treeArr;

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)
{
    node res;
    for (int ix = ql; ix <= qr; ix++)
    {
        if (treeArr[ix] > res.sufMax)
        {
            res.sufMax = treeArr[ix];
            res.mxIx = ix;
        }
        if (treeArr[ix] < res.sufMin)
        {
            res.sufMin = treeArr[ix];
            res.mnIx = ix;
        }
    }
    return res;
    /*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)
{
    for (int ix = ql; ix <= qr; ix++)
    {
        treeArr[ix] += v;
    }
    /*
    if (qr < l || r < ql)
        return;
    int m = l + (r - l) / 2;
    propagate(i);
    if (ql <= l && r <= qr)
    {
        lazy[i] += v;
        return;
    }
    add(2 * i, l, m, ql, qr, v);
    add(2 * i + 1, m + 1, r, ql, qr, v);*/
}

vi32 distribute_candies(vi32 c, vi32 l, vi32 r, vi32 v)
{
    int n = sz(c);
    int q = sz(l);

    treeArr = vi(q + 1);
    /*
    while (treeSz <= q)
        treeSz *= 2;
    tree.resize(treeSz * 2);
    lazy.resize(treeSz * 2);
    loop(q, 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;
                assert(s[i] >= 0);
            }
            else
            {
                s[i] = (i32)res.sufMax;
                assert(s[i] >= 0);
            }
        }
        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 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 11 ms 728 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5027 ms 29012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 5088 ms 15188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
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 Execution timed out 5045 ms 11712 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
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 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 11 ms 728 KB Output is correct
6 Execution timed out 5027 ms 29012 KB Time limit exceeded
7 Halted 0 ms 0 KB -