Submission #1069362

#TimeUsernameProblemLanguageResultExecution timeMemory
1069362BoasDistributing Candies (IOI21_candies)C++17
0 / 100
71 ms32336 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; #define int long long typedef vector<int> vi; typedef vector<signed> vi32; typedef vector<bool> vb; typedef vector<vi> vvi; typedef set<int> si; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; #define pb push_back #define loop(x, i) for (int i = 0; i < x; i++) #define rev(x, i) for (int i = (int)x - 1; i >= 0; i--) #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) #define sz(x) (int)x.size() vi32 distribute_candies(vi32 c, vi32 l, vi32 r, vi32 v) { int n = sz(c); int q = sz(l); vi32 s(n); vi sufSum(n + 1); vi sufMax(n + 1); vi sufMin(n + 1); vi diff(n + 1); // map<int,int> lastIx; rev(q, j) { assert(n - 1 == r[j]); sufSum[j] = sufSum[j + 1] + v[j]; sufMin[j] = min(sufMin[j + 1], sufSum[j]); sufMax[j] = max(sufMax[j + 1], sufSum[j]); diff[j] = sufMax[j] - sufMin[j]; } loop(n, i) { int ix = n - (lower_bound(RALL(diff), c[i]) - diff.rbegin()); if (ix == -1) { s[i] = sufSum[0]; continue; } if (sufSum[ix] == sufMax[ix]) { int mn = sufMin[ix]; int mnIx = upper_bound(ALL(sufMin), mn) - sufMin.begin() - 1; s[i] = c[i] + sufSum[mnIx]; } else { int mx = sufMax[ix]; int mxIx = n - (lower_bound(RALL(sufMax), mx) - sufMax.rbegin()); s[i] = sufSum[mxIx]; } } return s; }
#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...