oj.uz

Submission #733997

# Submission time Handle Problem Language Result Execution time Memory
733997 2023-05-01T13:09:38 Z benjaminkleyn Distributing Candies (IOI21_candies) C++17
100 / 100
 1963 ms 31060 KB 
#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 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)
    );
}

ll query(int c, int q)
{
    int lo = 0, hi = q + 1;
    while (lo < hi)
    {
        int mid = (lo + hi + 1) / 2;
        if (Max(1, 0, q + 1, mid, q + 1) - Min(1, 0, q + 1, mid, q + 1) <= c)
            hi = mid - 1;
        else
            lo = mid;
    }
    if (Max(1, 0, q + 1, lo + 1, q + 1) <= Max(1, 0, q + 1, lo, lo))
        return Max(1, 0, q + 1, q + 1, q + 1) - Min(1, 0, q + 1, lo + 1, q + 1);
    else
        return c - (Max(1, 0, q + 1, lo + 1, q + 1) - Max(1, 0, q + 1, q + 1, q + 1));
}

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, 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++;
        }
        s[i] = query(c[i], q);
    }

    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:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while (j < events.size() && events[j].idx <= i)
      |                ~~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 7 ms 604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1688 ms 29216 KB Output is correct
2 Correct 1690 ms 28536 KB Output is correct
3 Correct 1858 ms 28264 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 299 ms 25164 KB Output is correct
3 Correct 576 ms 6248 KB Output is correct
4 Correct 1944 ms 30244 KB Output is correct
5 Correct 1858 ms 30720 KB Output is correct
6 Correct 1963 ms 31060 KB Output is correct
7 Correct 1914 ms 30396 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 151 ms 24764 KB Output is correct
4 Correct 600 ms 4232 KB Output is correct
5 Correct 1622 ms 27848 KB Output is correct
6 Correct 1531 ms 28492 KB Output is correct
7 Correct 1566 ms 29140 KB Output is correct
8 Correct 1482 ms 27812 KB Output is correct
9 Correct 1584 ms 29352 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 1688 ms 29216 KB Output is correct
7 Correct 1690 ms 28536 KB Output is correct
8 Correct 1858 ms 28264 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 299 ms 25164 KB Output is correct
11 Correct 576 ms 6248 KB Output is correct
12 Correct 1944 ms 30244 KB Output is correct
13 Correct 1858 ms 30720 KB Output is correct
14 Correct 1963 ms 31060 KB Output is correct
15 Correct 1914 ms 30396 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 151 ms 24764 KB Output is correct
19 Correct 600 ms 4232 KB Output is correct
20 Correct 1622 ms 27848 KB Output is correct
21 Correct 1531 ms 28492 KB Output is correct
22 Correct 1566 ms 29140 KB Output is correct
23 Correct 1482 ms 27812 KB Output is correct
24 Correct 1584 ms 29352 KB Output is correct
25 Correct 0 ms 312 KB Output is correct
26 Correct 544 ms 4164 KB Output is correct
27 Correct 315 ms 24788 KB Output is correct
28 Correct 1637 ms 28920 KB Output is correct
29 Correct 1708 ms 29420 KB Output is correct
30 Correct 1846 ms 29516 KB Output is correct
31 Correct 1905 ms 29716 KB Output is correct
32 Correct 1760 ms 29880 KB Output is correct