oj.uz

Submission #734015

# Submission time Handle Problem Language Result Execution time Memory
734015 2023-05-01T13:39:13 Z benjaminkleyn Distributing Candies (IOI21_candies) C++17
100 / 100
 501 ms 31492 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)
    );
}

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

    vector<vector<pair<int,int>>> events(n+1);
    events[0].push_back({1000000000, -2});
    events[0].push_back({-1000000000, -1});
    for (int i = 0; i < q; i++)
    {
        events[l[i]].push_back({v[i], i});
        events[r[i]+1].push_back({-v[i], i});
    }
    vector<int> s(n);
    int j = 0; 
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (auto [val, time] : events[i])
        {
            sum += val;
            update(1, 0, q + 1, time + 2, q + 1, val);
        }
        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:98:9: warning: unused variable 'j' [-Wunused-variable]
   98 |     int j = 0;
      |         ^

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 31424 KB Output is correct
2 Correct 501 ms 31424 KB Output is correct
3 Correct 456 ms 31412 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 223 ms 21868 KB Output is correct
3 Correct 101 ms 7636 KB Output is correct
4 Correct 408 ms 31308 KB Output is correct
5 Correct 433 ms 31492 KB Output is correct
6 Correct 469 ms 31472 KB Output is correct
7 Correct 470 ms 31416 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 103 ms 20636 KB Output is correct
4 Correct 108 ms 7564 KB Output is correct
5 Correct 254 ms 27440 KB Output is correct
6 Correct 280 ms 27440 KB Output is correct
7 Correct 262 ms 27564 KB Output is correct
8 Correct 251 ms 27472 KB Output is correct
9 Correct 251 ms 27540 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 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 488 ms 31424 KB Output is correct
7 Correct 501 ms 31424 KB Output is correct
8 Correct 456 ms 31412 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 223 ms 21868 KB Output is correct
11 Correct 101 ms 7636 KB Output is correct
12 Correct 408 ms 31308 KB Output is correct
13 Correct 433 ms 31492 KB Output is correct
14 Correct 469 ms 31472 KB Output is correct
15 Correct 470 ms 31416 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 103 ms 20636 KB Output is correct
19 Correct 108 ms 7564 KB Output is correct
20 Correct 254 ms 27440 KB Output is correct
21 Correct 280 ms 27440 KB Output is correct
22 Correct 262 ms 27564 KB Output is correct
23 Correct 251 ms 27472 KB Output is correct
24 Correct 251 ms 27540 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 114 ms 7636 KB Output is correct
27 Correct 215 ms 21836 KB Output is correct
28 Correct 465 ms 31436 KB Output is correct
29 Correct 466 ms 31416 KB Output is correct
30 Correct 477 ms 31344 KB Output is correct
31 Correct 451 ms 31304 KB Output is correct
32 Correct 466 ms 31324 KB Output is correct