Submission #437686

#	Time	Username	Problem	Language	Result	Execution time	Memory
437686		SHZhang	Distributing Candies (IOI21_candies)	C++17	67 / 100	5037 ms	25692 KiB

candies

#include "candies.h"

#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>

#define ll long long

using namespace std;

#define BLKSIZE 500

int n, q;

int c[200005];
int l[200005], r[200005];
int v[200005];
int ans[200005];
// amount from empty vs. cap
vector<pair<ll, ll> > funcs[200005];
vector<ll> funcpsum[200005];
ll reclow[200005], rechigh[200005];

void work(int from, int to)
{
    //fprintf(stderr, "%d %d\n", from, to);
    vector<int> usefuncs;
    int curfunc = 0; funcs[0].clear();
    reclow[0] = rechigh[0] = 0;
    ll curv = 0;
    for (int i = 1; i <= q; i++) {
        if (r[i] < from || l[i] > to) continue;
        if (l[i] <= from && to <= r[i]) {
            curv += v[i];
            reclow[curfunc] = min(reclow[curfunc], curv);
            rechigh[curfunc] = max(rechigh[curfunc], curv);
            ll base_value = 0;
            if (v[i] > 0) {
                //int curback = 0;
                while (!funcs[curfunc].empty() && funcs[curfunc].back().first - base_value <= v[i]) {
                    base_value += funcs[curfunc].back().second - funcs[curfunc].back().first;
                    //curback = funcs[curfunc].back().second;
                    funcs[curfunc].pop_back();
                }
                funcs[curfunc].push_back(make_pair(0, v[i] + base_value));
            } else {
                while (!funcs[curfunc].empty() && funcs[curfunc].back().second - funcs[curfunc].back().first + base_value <= -v[i]) {
                    base_value += funcs[curfunc].back().second - funcs[curfunc].back().first;
                    funcs[curfunc].pop_back();
                }
                if (!funcs[curfunc].empty()) {
                    funcs[curfunc][funcs[curfunc].size() - 1].first += -v[i] - base_value;
                }
            }
            /*for (int x = 0; x <= curfunc; x++) {
                fprintf(stderr, "func %d: ", x);
                for (int j = 0; j < funcs[x].size(); j++) {
                    fprintf(stderr, "(%d, %d) ",  funcs[x][j].first, funcs[x][j].second);
                }
            }*/
        } else {
            usefuncs.push_back(curfunc);
            usefuncs.push_back(-i);
            curfunc++; funcs[curfunc].clear();
            reclow[curfunc] = rechigh[curfunc] = 0;
            curv = 0;
        }
    }
    usefuncs.push_back(curfunc);
    for (int i = 0; i <= curfunc; i++) {
        reverse(funcs[i].begin(), funcs[i].end());
        //fprintf(stderr, "func %d: ", i);
        funcpsum[i].resize(funcs[i].size()); // ?
        ll cursum = 0;
        for (int j = 0; j < funcs[i].size(); j++) {
            //fprintf(stderr, "(%d, %d) ",  funcs[i][j].first, funcs[i][j].second);
            cursum += funcs[i][j].second - funcs[i][j].first;
            funcpsum[i][j] = cursum;
        }
        //fprintf(stderr, "\n");
    }
    for (int i = from; i <= to; i++) {
        for (int j = 0; j < usefuncs.size(); j++) {
            if (usefuncs[j] < 0) {
                int opid = -usefuncs[j];
                if (l[opid] <= i && i <= r[opid]) {
                    ans[i] += v[opid];
                    if (ans[i] < 0) ans[i] = 0;
                    if (ans[i] > c[i]) ans[i] = c[i];
                }
            } else {
                int fid = usefuncs[j];
                ll funcval;
                if (funcs[fid].empty() || c[i] <= funcs[fid][0].first) {
                    funcval = 0;
                } else {
                    int L = 0; int R = (int)(funcs[fid].size()) - 1;
                    while (L < R) {
                        int mid = (L + R) / 2 + 1;
                        if (funcs[fid][mid].first <= c[i]) {
                            L = mid;
                        } else {
                            R = mid - 1;
                        }
                    }
                    if (funcs[fid][L].second <= c[i]) {
                        funcval = funcpsum[fid][L];
                    } else {
                        funcval = funcpsum[fid][L] - (funcs[fid][L].second - c[i]);
                    }
                }
                ll switchval_low = -reclow[fid];
                ll switchval_high = (ll)c[i] - rechigh[fid];
                //fprintf(stderr, "%d %d %lld %lld\n", funcpsum[fid][0], funcval, switchval_low, switchval_high);
                if (switchval_high < switchval_low || ans[i] < switchval_low) {
                    ans[i] = funcval;
                } else {
                    ans[i] = (ll)funcval - switchval_low + min((ll)ans[i], switchval_high);
                }
            }
        }
    }
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
    n = (int)C.size(); q = (int)L.size();
    for (int i = 1; i <= n; i++) {
        c[i] = C[i-1];
    }
    for (int i = 1; i <= q; i++) {
        l[i] = L[i-1] + 1;
        r[i] = R[i-1] + 1;
        v[i] = V[i-1];
    }
    for (int i = 1; i <= n; i += BLKSIZE) {
        work(i, min(i + BLKSIZE - 1, n));
    }
    vector<int> ansvec(n);
    for (int i = 0; i < n; i++) ansvec[i] = ans[i+1];
    return ansvec;
}

Compilation message (stderr)

candies.cpp: In function 'void work(int, int)':
candies.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = 0; j < funcs[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
candies.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int j = 0; j < usefuncs.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~

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