oj.uz

Submission #734012

# Submission time Handle Problem Language Result Execution time Memory
734012 2023-05-01T13:34:22 Z benjaminkleyn Distributing Candies (IOI21_candies) C++17
100 / 100
 453 ms 24376 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,bmi,bmi2")
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll M[1000000] = {0}, m[1000000] = {0}, lazy[1000000] = {0};

void push(int v)
{
    M[2 * v] += lazy[v];
    M[2 * v + 1] += lazy[v];

    m[2 * v] += lazy[v];
    m[2 * v + 1] += lazy[v];

    lazy[2 * v] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, ll dx)
{
    if (r < tl || tr < l)
        return;
    if (l <= tl && tr <= r)
    {
        M[v] += dx;
        m[v] += dx;
        lazy[v] += dx;
        return;
    }

    push(v);
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, r, dx);
    update(2 * v + 1, tm + 1, tr, l, r, dx);
    M[v] = max(M[2 * v], M[2 * v + 1]);
    m[v] = min(m[2 * v], m[2 * v + 1]);
}

ll Find(int v, int tl, int tr, ll Mx, ll Mn, int c)
{
    if (tl == tr)
        return tl;

    push(v);
    int tm = (tl + tr) / 2;
    if (max(Mx, M[2 * v + 1]) - min(Mn, m[2 * v + 1]) <= c)
        return Find(2 * v, tl, tm, max(Mx, M[2 * v + 1]), min(Mn, m[2 * v + 1]), c);
    return Find(2 * v + 1, tm + 1, tr, Mx, Mn, c);
}

ll Max(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l)
        return LLONG_MIN;
    if (l <= tl && tr <= r)
        return M[v];

    push(v);
    int tm = (tl + tr) / 2;
    return max(
        Max(2 * v, tl, tm, l, r),
        Max(2 * v + 1, tm + 1, tr, l, r)
    );
}

ll Min(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l)
        return LLONG_MAX;
    if (l <= tl && tr <= r)
        return m[v];

    push(v);
    int tm = (tl + tr) / 2;
    return min(
        Min(2 * v, tl, tm, l, r),
        Min(2 * v + 1, tm + 1, tr, l, r)
    );
}

struct Event
{
    int idx, val, time;
};
bool operator<(const Event &A, const Event &B)
{
    return A.idx < B.idx;
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) 
{
    int n = c.size(), q = v.size();

    vector<Event> events;
    events.push_back({-2, 1000000000, -2});
    events.push_back({-1, -1000000000, -1});
    for (int i = 0; i < q; i++)
    {
        events.push_back({l[i], v[i], i});
        events.push_back({r[i] + 1, -v[i], i});
    }
    sort(events.begin(), events.end());
    vector<int> s(n);
    int j = 0; 
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        while (j < events.size() && events[j].idx <= i)
        {
            sum += events[j].val;
            update(1, 0, q + 1, events[j].time + 2, q + 1, events[j].val);
            j++;
        }
        int idx = Find(1, 0, q + 1, sum, sum, c[i]);

        if (Max(1, 0, q + 1, idx + 1, q + 1) <= Max(1, 0, q + 1, idx, idx))
            s[i] = sum - Min(1, 0, q + 1, idx + 1, q + 1);
        else
            s[i] = c[i] - (Max(1, 0, q + 1, idx + 1, q + 1) - sum);
    }

    return s;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         while (j < events.size() && events[j].idx <= i)
      |                ~~^~~~~~~~~~~~~~~

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 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 4 ms 580 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 24340 KB Output is correct
2 Correct 453 ms 24368 KB Output is correct
3 Correct 431 ms 24348 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 210 ms 22088 KB Output is correct
3 Correct 101 ms 4028 KB Output is correct
4 Correct 370 ms 24368 KB Output is correct
5 Correct 406 ms 24368 KB Output is correct
6 Correct 399 ms 24372 KB Output is correct
7 Correct 405 ms 24376 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 212 KB Output is correct
3 Correct 115 ms 22100 KB Output is correct
4 Correct 105 ms 2996 KB Output is correct
5 Correct 272 ms 24276 KB Output is correct
6 Correct 269 ms 24292 KB Output is correct
7 Correct 325 ms 24280 KB Output is correct
8 Correct 280 ms 24364 KB Output is correct
9 Correct 271 ms 24276 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 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 4 ms 580 KB Output is correct
6 Correct 420 ms 24340 KB Output is correct
7 Correct 453 ms 24368 KB Output is correct
8 Correct 431 ms 24348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 210 ms 22088 KB Output is correct
11 Correct 101 ms 4028 KB Output is correct
12 Correct 370 ms 24368 KB Output is correct
13 Correct 406 ms 24368 KB Output is correct
14 Correct 399 ms 24372 KB Output is correct
15 Correct 405 ms 24376 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 115 ms 22100 KB Output is correct
19 Correct 105 ms 2996 KB Output is correct
20 Correct 272 ms 24276 KB Output is correct
21 Correct 269 ms 24292 KB Output is correct
22 Correct 325 ms 24280 KB Output is correct
23 Correct 280 ms 24364 KB Output is correct
24 Correct 271 ms 24276 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 102 ms 2892 KB Output is correct
27 Correct 239 ms 22152 KB Output is correct
28 Correct 417 ms 24364 KB Output is correct
29 Correct 408 ms 24280 KB Output is correct
30 Correct 400 ms 24276 KB Output is correct
31 Correct 412 ms 24364 KB Output is correct
32 Correct 430 ms 24276 KB Output is correct