oj.uz

Submission #831922

# Submission time Handle Problem Language Result Execution time Memory
831922 2023-08-20T17:41:52 Z Johann Distributing Candies (IOI21_candies) C++17
27 / 100
 305 ms 32800 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, Q;
vi C, L, R, V;
vector<int> ans;

struct operation
{
    int op;     // -1 or 1: inner min or inner max
    ll a, b, d; // -1: max(min(x + a, b), d) or 1: min(max(x + a, b), d)
    void swap()
    {
        ll oldD = d;
        if (op == -1)
            d = max(oldD, b);
        else
            d = min(oldD, b);
        op *= -1;
        b = oldD;
    }
    ll eval(ll x)
    {
        if (op == 1)
            swap();
        return max(min(x + a, b), d);
    }
};
struct segtree
{
    int size;
    vector<operation> arr;
    ll c;
    void init(int _size, int _c)
    {
        c = _c;
        size = 1;
        while (size < _size)
            size *= 2;
        arr.assign(2 * size, {1, 0, 0, c});
    }
    operation apply(operation a, operation b)
    {
        // b(a(x))
        if (a.op != -1)
            a.swap();
        if (b.op != 1)
            b.swap();
        ll tmp = max(a.d + b.a, b.b);
        operation ret;
        ret.op = 1;
        ret.a = a.a + b.a;
        ret.b = tmp;
        ret.d = min(max(tmp, a.b + b.a), b.d);
        return ret;
    }
    void propagate(int x)
    {
        assert(x < size);
        arr[2 * x] = apply(arr[2 * x], arr[x]);
        arr[2 * x + 1] = apply(arr[2 * x + 1], arr[x]);
        arr[x] = {-1, 0, c, 0};
    }
    void update(int l, int r, ll v)
    {
        if (v > 0)
            update(l, r, {-1, v, c, 0}, 1, 0, size);
        else
            update(l, r, {1, v, 0, c}, 1, 0, size);
    }
    void update(int l, int r, operation op, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            arr[x] = apply(arr[x], op);
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        propagate(x);
        update(l, r, op, 2 * x, lx, m);
        update(l, r, op, 2 * x + 1, m, rx);
    }
    void queryAns() { queryAns(1, 0, size); }
    void queryAns(int x, int lx, int rx)
    {
        if (x >= size)
        {
            if (lx < sz(ans))
                ans[lx] = arr[x].eval(0);
            return;
        }
        propagate(x);
        int m = (lx + rx) / 2;
        queryAns(2 * x, lx, m);
        queryAns(2 * x + 1, m, rx);
    }
};
segtree seg;

std::vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    C = vi(all(c));
    N = sz(c);
    Q = sz(l);

    seg.init(N, C[0]);

    for (int q = 0; q < Q; ++q)
        seg.update(l[q], ++r[q], v[q]);

    ans.resize(N);
    seg.queryAns();

    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 27124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 128 ms 6616 KB Output is correct
3 Correct 51 ms 24672 KB Output is correct
4 Correct 284 ms 32012 KB Output is correct
5 Correct 288 ms 32400 KB Output is correct
6 Correct 281 ms 32800 KB Output is correct
7 Correct 305 ms 32148 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -