Submission #437686

#TimeUsernameProblemLanguageResultExecution timeMemory
437686SHZhangDistributing Candies (IOI21_candies)C++17
67 / 100
5037 ms25692 KiB
#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++) {
      |                         ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...