Submission #734015

#	Time	Username	Problem	Language	Result	Execution time	Memory
734015		benjaminkleyn	Distributing Candies (IOI21_candies)	C++17	100 / 100	501 ms	31492 KiB

candies

#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 (stderr)

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33