| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 244731 |
2020-07-04T19:04:37 Z |
Berted |
Holiday (IOI14_holiday) |
C++14 |
|
935 ms |
7392 KB |
#include "holiday.h"
#include <iostream>
#include <vector>
#include <map>
#include <bitset>
#include <algorithm>
#include <assert.h>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second
const ll MN = -1e18;
const int SZ = 1 << 18;
using namespace std;
int n, s, d, ar[100001], idx[100001];
bitset<100001> used;
pii srt[100001] = {};
ll seg[SZ][2] = {}, ret = 0;
void bld(int idx, int L, int R)
{
//cout << "B " << idx << " " << L << " " << R << "\n";
seg[idx][0] = seg[idx][1] = 0;
if (L < R)
{
int M = L + R >> 1;
bld(2 * idx, L, M); bld(2 * idx + 1, M + 1, R);
}
else {used[L] = 0;}
}
inline void upd(int idx, int L, int R, int x)
{
if (L <= R)
{
if (L == R)
{
if (seg[idx][1]) {seg[idx][0] = 0; seg[idx][1] = 0; used[L] = 0;}
else {seg[idx][1] = 1; seg[idx][0] = srt[L].fst; used[L] = 1;}
}
else
{
int M = L + R >> 1;
if (x <= M) upd(2 * idx, L, M, x);
else upd(2 * idx + 1, M + 1, R, x);
seg[idx][0] = seg[2 * idx][0] + seg[2 * idx + 1][0];
seg[idx][1] = seg[2 * idx][1] + seg[2 * idx + 1][1];
}
//cout << "U " << L << " " << R << " - " << x << " -- " << seg[idx][0] << " " << seg[idx][1] << "\n";
}
}
inline ll qry(int idx, int L, int R, int k)
{
if (k <= 0) return 0;
if (L <= R)
{
//cout << "Q " << L << " " << R << " " << k << "\n";
if (L == R) {return seg[idx][0];}
else
{
int M = L + R >> 1;
if (seg[2 * idx][1] >= k) return qry(2 * idx, L, M, k);
else return qry(2 * idx + 1, M + 1, R, k - seg[2 * idx][1]) + seg[2 * idx][0];
}
}
}
void computeL(int l, int r, int p, int optL, int optR)
{
if (l <= r)
{
int m = l + r >> 1;
//cout << "CL " << l << " " << r << " " << p << " " << optL << " " << optR << "\n";
if (m < p) {for (int i = m; i < p; i++) upd(1, 0, n - 1, idx[i]);}
else {for (int i = p; i < m; i++) upd(1, 0, n - 1, idx[i]);}
ll optVal = 0, optP = optL, cr;
for (int i = optL; i <= optR; i++)
{
if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
//cout << i << " " << d - 2 * (s - m) - (i - s) << "\n";
cr = qry(1, 0, n - 1, d - 2 * (s - m) - (i - s));
//cout << cr << "\n";
if (cr > optVal) {optVal = cr; optP = i;}
}
for (int i = optL; i <= optR; i++) {upd(1, 0, n - 1, idx[i]);}
ret = max(ret, optVal);
computeL(l, m - 1, m, optL, optP);
computeL(m + 1, r, m, optP, optR);
if (m < p) {for (int i = m; i < p; i++) upd(1, 0, n - 1, idx[i]);}
else {for (int i = p; i < m; i++) upd(1, 0, n - 1, idx[i]);}
}
else
{
for (int i = optL; i <= optR; i++)
{
if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
}
}
}
void computeR(int l, int r, int p, int optL, int optR)
{
if (l <= r)
{
int m = l + r >> 1;
//cout << "CR " << l << " " << r << " " << optL << " " << optR << "\n";
if (m > p) for (int i = m; i > p; i--) upd(1, 0, n - 1, idx[i]);
else for (int i = p; i > m; i--) upd(1, 0, n - 1, idx[i]);
ll optVal = 0, optP = optR, cr;
for (int i = optR; i >= optL; i--)
{
if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
cr = qry(1, 0, n - 1, d - 2 * (m - s) - (s - i));
//cout << i << " " << d - 2 * (m - s) - (s - i) << "\n";
//cout << cr << "\n";
if (cr > optVal) {optVal = cr; optP = i;}
}
for (int i = optR; i >= optL; i--) {upd(1, 0, n - 1, idx[i]);}
ret = max(ret, optVal);
computeR(m + 1, r, m, optP, optR);
computeR(l, m - 1, m, optL, optP);
if (m > p) for (int i = m; i > p; i--) upd(1, 0, n - 1, idx[i]);
else for (int i = p; i > m; i--) upd(1, 0, n - 1, idx[i]);
}
else
{
for (int i = optR; i >= optL; i--)
{
if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
}
}
}
ll findMaxAttraction(int N, int S, int D, int A[])
{
n = N; d = D; s = S;
for (int i = 0; i < n; i++) {ar[i] = A[i]; srt[i] = make_pair(A[i], i);}
sort(srt, srt + n, greater<pii>());
for (int i = 0; i < n; i++)
{
idx[srt[i].snd] = i;
//cout << srt[i].snd << " -> " << i << "\n";
}
//cout << "Here\n";
if (d) ret = ar[s];
bld(1, 0, n - 1);
computeL(0, s, s + 1, s + 1, n - 1);
bld(1, 0, n - 1);
computeR(s, n - 1, s - 1, 0, s - 1);
return ret;
}
/*
const int SZ = 1 << 17;
int n, fwk[2][SZ + 1] = {};
long long dp[2][9001] = {}, mxL[9001] = {}, mxR[9001] = {}, mxcL[9001] = {}, mxcR[9001] = {};
map<pair<int, int>, int> mp;
inline void upd(int t, int x, int v)
{
for (; x < SZ; x += x & (-x)) fwk[t][x] += v;
}
inline int qry(int t, int x)
{
int ret = 0;
for (; x; x -= x & (-x)) ret += fwk[t][x];
return ret;
}
inline int fd(int x)
{
int to = 0, pv = 0;
for (int i = SZ >> 1; i; i >>= 1)
{
//cout << i << " " << pv << " " << fwk[0][i + pv] << " " << to << " " << x << "\n";
if (to + fwk[0][i + pv] <= x) {to += fwk[0][i + pv]; pv += i;}
}
return pv;
}
long long int findMaxAttraction(int N, int S, int D, int A[]) { //Sub - 2
assert(S == 0);
n = N;
for (int i = 0; i < n; i++) {mp[make_pair(A[i], i)] = 1;}
int p = n;
long long int ans = 0;
for (auto &x : mp) {x.second = p--;}
for (int i = 0; i < min(D + 1, n); i++)
{
upd(0, mp[make_pair(A[i], i)], 1);
upd(1, mp[make_pair(A[i], i)], A[i]);
int idx = fd(D - i);
ans = max(ans, (long long)qry(1, idx));
}
return ans;
}
long long int findMaxAttraction(int N, int S, int D, int A[]) { //Sub 1-3
assert(n <= 3000);
n = N;
ll ans = 0;
for (int i = 0; i <= D; i++) dp[S & 1][i] = MN;
dp[S & 1][0] = 0;
dp[S & 1][1] = A[S];
mxL[1] = A[S];
for (int i = S - 1; i >= 0; i--)
{
int ns = i & 1, os = !ns;
for (int k = 0; k < (S - i); k++) dp[ns][k] = MN;
for (int k = S - i; k <= D; k++)
{
dp[ns][k] = MN;
dp[ns][k] = max(dp[ns][k - 1], dp[os][k - 1]);
if (k > 1)
{
dp[ns][k] = max(dp[ns][k], dp[os][k - 2] + A[i]);
}
mxL[k] = max(mxL[k], dp[ns][k]);
}
}
for (int i = 0; i <= D; i++) dp[S & 1][i] = MN;
dp[S & 1][0] = 0;
dp[S & 1][1] = A[S];
mxcL[1] = A[S];
for (int i = S - 1; i >= 0; i--)
{
int ns = i & 1, os = !ns;
for (int k = 0; k < 2 * (S - i); k++) dp[ns][k] = MN;
for (int k = 2 * (S - i); k <= D; k++)
{
dp[ns][k] = MN;
dp[ns][k] = max(dp[ns][k - 2], dp[os][k - 2]);
if (k > 2)
{
dp[ns][k] = max(dp[ns][k], dp[os][k - 3] + A[i]);
}
mxcL[k] = max(mxcL[k], dp[ns][k]);
}
}
for (int i = 0; i <= D; i++) dp[~S & 1][i] = MN;
dp[~S & 1][1] = 0;
dp[~S & 1][2] = A[S + 1];
mxR[2] = A[S + 1];
for (int i = S + 2; i < n; i++)
{
int ns = i & 1, os = !ns;
for (int k = 0; k < i - S; k++) dp[ns][k] = MN;
for (int k = (i - S); k <= D; k++)
{
dp[ns][k] = max(dp[ns][k - 1], dp[os][k - 1]);
if (k > 1)
{
dp[ns][k] = max(dp[ns][k], dp[os][k - 2] + A[i]);
}
mxR[k] = max(mxR[k], dp[ns][k]);
//cout << "DPR " << i << " " << k << " " << dp[ns][k] << " " << mxR[k] << "\n";
}
}
for (int i = 0; i <= D; i++) dp[~S & 1][i] = MN;
dp[~S & 1][2] = 0;
dp[~S & 1][3] = A[S + 1];
mxcR[3] = A[S + 1];
for (int i = S + 2; i < n; i++)
{
int ns = i & 1, os = !ns;
for (int k = 0; k < 2 * (i - S); k++) dp[ns][k] = MN;
for (int k = 2 * (i - S); k <= D; k++)
{
dp[ns][k] = MN;
dp[ns][k] = max(dp[ns][k - 2], dp[os][k - 2]);
if (k > 2)
{
dp[ns][k] = max(dp[ns][k], dp[os][k - 3] + A[i]);
}
mxcR[k] = max(mxcR[k], dp[ns][k]);
}
}
for (int i = 0; i <= D; i++)
{
ans = max(ans, mxcR[i] + mxL[D - i]);
ans = max(ans, mxcL[i] + mxR[D - i]);
//cout << i << " " << mxcR[i] << " " << mxL[D - i] << " " << mxcL[i] << " " << mxR[D - i] << "\n";
}
return ans;
}
*/
Compilation message
holiday.cpp: In function 'void bld(int, int, int)':
holiday.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int M = L + R >> 1;
~~^~~
holiday.cpp: In function 'void upd(int, int, int, int)':
holiday.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int M = L + R >> 1;
~~^~~
holiday.cpp: In function 'long long int qry(int, int, int, int)':
holiday.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int M = L + R >> 1;
~~^~~
holiday.cpp: In function 'void computeL(int, int, int, int, int)':
holiday.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
holiday.cpp: In function 'void computeR(int, int, int, int, int)':
holiday.cpp:112:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
holiday.cpp: In function 'long long int qry(int, int, int, int)':
holiday.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
6648 KB |
Output is correct |
| 2 |
Correct |
230 ms |
6632 KB |
Output is correct |
| 3 |
Correct |
229 ms |
6528 KB |
Output is correct |
| 4 |
Correct |
233 ms |
6648 KB |
Output is correct |
| 5 |
Correct |
311 ms |
6676 KB |
Output is correct |
| 6 |
Correct |
84 ms |
2056 KB |
Output is correct |
| 7 |
Correct |
155 ms |
3584 KB |
Output is correct |
| 8 |
Correct |
193 ms |
3840 KB |
Output is correct |
| 9 |
Correct |
57 ms |
1912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
512 KB |
Output is correct |
| 2 |
Correct |
11 ms |
512 KB |
Output is correct |
| 3 |
Correct |
9 ms |
640 KB |
Output is correct |
| 4 |
Correct |
16 ms |
512 KB |
Output is correct |
| 5 |
Correct |
15 ms |
512 KB |
Output is correct |
| 6 |
Correct |
7 ms |
384 KB |
Output is correct |
| 7 |
Correct |
8 ms |
384 KB |
Output is correct |
| 8 |
Correct |
8 ms |
384 KB |
Output is correct |
| 9 |
Correct |
8 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
7392 KB |
Output is correct |
| 2 |
Correct |
230 ms |
7296 KB |
Output is correct |
| 3 |
Correct |
320 ms |
3832 KB |
Output is correct |
| 4 |
Correct |
17 ms |
512 KB |
Output is correct |
| 5 |
Correct |
8 ms |
384 KB |
Output is correct |
| 6 |
Correct |
8 ms |
384 KB |
Output is correct |
| 7 |
Correct |
8 ms |
384 KB |
Output is correct |
| 8 |
Correct |
910 ms |
7160 KB |
Output is correct |
| 9 |
Correct |
935 ms |
7288 KB |
Output is correct |
