Submission #636351

#TimeUsernameProblemLanguageResultExecution timeMemory
636351SirCovidThe19thHoliday (IOI14_holiday)C++17
100 / 100
554 ms9648 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mx = 1e5 + 5; int n, d, start, pos[mx], A[mx]; pair<int, int> S[mx]; ll ans, F[2][2][mx * 3], bit[mx][2]; void upd(int i, int type){ for (int j = pos[i]; j < mx; j += j & (-j)) bit[j][0] += type * A[i], bit[j][1] += type; } ll qry(int k){ ll ret = 0; for (int pw = (1 << 17), pos = 0; pw; pw /= 2) if (pos + pw < mx and bit[pos + pw][1] <= k){ pos += pw; ret += bit[pos][0]; k -= bit[pos][1]; } return ret; } void dnq(int l, int r, int stopL, int stopR, bool dir, bool rep){ if (l > r or stopL > stopR) return; for (int i = stopL; i <= stopR; i++) upd(i, -1); int midD = (l + r) / 2, stopMid = -1; for (int stop = stopL; stop <= stopR; stop++){ int visit = midD - (stop - start) * (rep ? 2 : 1); upd(stop, 1); if (visit < 0) continue; ll val = qry(visit); if (val >= F[dir][rep][midD]){ F[dir][rep][midD] = val; stopMid = stop; } } for (int i = stopMid + 1; i <= stopR; i++) upd(i, -1); dnq(l, midD - 1, stopL, stopMid, dir, rep); for (int i = stopMid + 1; i <= stopR; i++) upd(i, 1); dnq(midD + 1, r, stopMid, stopR, dir, rep); } void work(int tmpSt, int tmpA[], bool dir, bool rep){ start = tmpSt; for (int i = 0; i < n; i++){ A[i] = tmpA[i]; S[i] = {tmpA[i], i}; } sort(S, S + n, greater<pair<int, int>>()); for (int i = 0; i < n; i++) pos[S[i].second] = i + 1; //BIT has to be 1 indexed memset(bit, 0, sizeof(bit)); for (int i = start; i < n; i++) upd(i, 1); dnq(0, d, start, n - 1, dir, rep); } ll findMaxAttraction(int tmpN, int tmpSt, int tmpD, int tmpA[]){ n = tmpN; d = tmpD; work(tmpSt, tmpA, 0, 0); work(tmpSt + 1, tmpA, 0, 1); reverse(tmpA, tmpA + n); work(n - tmpSt - 1, tmpA, 1, 0); work(n - tmpSt, tmpA, 1, 1); for (int i = 0; i <= d - 2; i++) ans = max({ans, F[0][1][i] + F[1][0][d - i - 2], F[1][1][i] + F[0][0][d - i - 2]}); return max({ans, F[0][0][d], F[1][0][d]}); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...