Submission #1063079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063079		fv3	Distributing Candies (IOI21_candies)	C++17	29 / 100	168 ms	36188 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int nt = 1;
vector<ll> st_mx, st_mn;

ll get_range_mx(int l, int r, int k, int x, int y)
{
    if (y < l || x > r) return -(1ll << 60);
    if (x >= l && y <= r) return st_mx[k];
    int c = (x + y) / 2;
    return max(get_range_mx(l, r, k*2, x, c), get_range_mx(l, r, k*2|1, c+1, y));
}

ll get_range_mn(int l, int r, int k, int x, int y)
{
    if (y < l || x > r) return 1ll << 60;
    if (x >= l && y <= r) return st_mn[k];
    int c = (x + y) / 2;
    return min(get_range_mn(l, r, k*2, x, c), get_range_mn(l, r, k*2|1, c+1, y));
}

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

    vector<pair<ll, int>> box(N);
    for (int i = 0; i < N; i++)
        box[i] = {c[i], i};
    sort(box.begin(), box.end());
    reverse(box.begin(), box.end());

    while (nt <= Q) nt <<= 1;
    st_mx = vector<ll>(nt * 2, -(1ll << 60));
    st_mn = vector<ll>(nt * 2, 1ll << 60);

    ll sum = 0;
    map<ll, int> ps_pos;
    for (int i = 0; i < Q; i++)
    {
        sum += v[i];
        st_mx[i + nt + 1] = sum;
        st_mn[i + nt + 1] = sum;
        ps_pos[sum] = i + 1;
    }

    st_mn = st_mx;    for (int i = nt - 1; i >= 1; i--)
        st_mx[i] = max(st_mx[i*2], st_mx[i*2|1]);
    for (int i = nt - 1; i >= 1; i--)
        st_mn[i] = min(st_mn[i*2], st_mn[i*2|1]);

    int time = 0; int score = 0;
    bool minimized = true;
    for (int i = 0; i < Q; i++)
    {
        score += v[i];
        if (score <= 0)
        {
            time = i + 1;
            score = 0;
            minimized = true;
        }
        else if (score >= box[0].first)
        {
            time = i + 1;
            score = box[0].first;
            minimized = false;
        }
    }
    vector<int> res(N);
    res[box[0].second] = score;

    for (int i = 1; i < N; i++)
    {
        while (true)
        {
            ll now = st_mx[nt + time];
            bool ok = false;
            if (minimized)
            {
                ll mx = get_range_mx(time, Q, 1, 0, nt - 1); 
                if (mx - now >= (ll)box[i].first)
                {
                    time = ps_pos[mx];
                    minimized = false;
                    ok = true;
                }
            }
            else
            {
                ll mn = get_range_mn(time, Q, 1, 0, nt - 1); 
                if (box[i].first - (now - mn) <= 0ll)
                {
                    time = ps_pos[mn];
                    minimized = true;
                    ok = true;
                }
            }
            if (!ok) break;
        }
        
        res[box[i].second] = st_mx[nt + Q] - st_mx[nt + time];
        if (!minimized)
            res[box[i].second] += box[i].first;

    }

    return res;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33