oj.uz

Submission #437688

# Submission time Handle Problem Language Result Execution time Memory
437688 2021-06-26T21:27:06 Z SHZhang Distributing Candies (IOI21_candies) C++17
100 / 100
 3771 ms 26464 KB 
#include "candies.h"

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

#define ll long long

using namespace std;

#define BLKSIZE 215

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)
{
    //fprintf(stderr, "HELLO");
    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));
        //fprintf(stderr, "HELLO");
    }
    vector<int> ansvec(n);
    for (int i = 0; i < n; i++) ansvec[i] = ans[i+1];
    return ansvec;
}

Compilation message

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 8 ms 9832 KB Output is correct
4 Correct 11 ms 9804 KB Output is correct
5 Correct 18 ms 9900 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2855 ms 21148 KB Output is correct
2 Correct 2947 ms 21064 KB Output is correct
3 Correct 2901 ms 21100 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 1479 ms 21140 KB Output is correct
3 Correct 93 ms 15156 KB Output is correct
4 Correct 3302 ms 21048 KB Output is correct
5 Correct 3374 ms 21060 KB Output is correct
6 Correct 3301 ms 20996 KB Output is correct
7 Correct 2570 ms 20932 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 97 ms 17164 KB Output is correct
4 Correct 86 ms 14008 KB Output is correct
5 Correct 2814 ms 21040 KB Output is correct
6 Correct 2793 ms 21012 KB Output is correct
7 Correct 2895 ms 20884 KB Output is correct
8 Correct 2842 ms 20880 KB Output is correct
9 Correct 2551 ms 20892 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 8 ms 9832 KB Output is correct
4 Correct 11 ms 9804 KB Output is correct
5 Correct 18 ms 9900 KB Output is correct
6 Correct 2855 ms 21148 KB Output is correct
7 Correct 2947 ms 21064 KB Output is correct
8 Correct 2901 ms 21100 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 1479 ms 21140 KB Output is correct
11 Correct 93 ms 15156 KB Output is correct
12 Correct 3302 ms 21048 KB Output is correct
13 Correct 3374 ms 21060 KB Output is correct
14 Correct 3301 ms 20996 KB Output is correct
15 Correct 2570 ms 20932 KB Output is correct
16 Correct 7 ms 9676 KB Output is correct
17 Correct 7 ms 9676 KB Output is correct
18 Correct 97 ms 17164 KB Output is correct
19 Correct 86 ms 14008 KB Output is correct
20 Correct 2814 ms 21040 KB Output is correct
21 Correct 2793 ms 21012 KB Output is correct
22 Correct 2895 ms 20884 KB Output is correct
23 Correct 2842 ms 20880 KB Output is correct
24 Correct 2551 ms 20892 KB Output is correct
25 Correct 7 ms 9616 KB Output is correct
26 Correct 90 ms 14012 KB Output is correct
27 Correct 1613 ms 21324 KB Output is correct
28 Correct 3741 ms 21116 KB Output is correct
29 Correct 3771 ms 25708 KB Output is correct
30 Correct 3583 ms 26100 KB Output is correct
31 Correct 3551 ms 26232 KB Output is correct
32 Correct 3465 ms 26464 KB Output is correct