| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 297850 |
2020-09-12T05:01:56 Z |
juckter |
Holiday (IOI14_holiday) |
C++14 |
|
2142 ms |
18168 KB |
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
struct node {
int l, r;
ll cnt, val;
node *left, *right;
node(int l, int r, int c = 0, ll v = 0) : l(l), r(r), cnt(c), val(v), left(nullptr), right(nullptr) {
if(l != r) {
int m = (l + r) / 2;
left = new node(l, m);
right = new node(m + 1, r);
}
}
~node() {
delete left;
delete right;
}
void upd(int p, ll v) {
if(p < l || r < p)
return;
if(l == r) {
if(v == -1) {
val = 0;
cnt = 0;
}
else {
val = v;
cnt = 1;
}
return;
}
left->upd(p, v);
right->upd(p, v);
cnt = left->cnt + right->cnt;
val = left->val + right->val;
}
ll bsum(ll amt) {
//cerr << amt << " " << l << " " << r << endl;
if(amt == 0)
return 0;
if(amt >= cnt)
return val;
if(amt <= right->cnt)
return right->bsum(amt);
return right->val + left->bsum(amt - right->cnt);
}
void dbg() {
//cerr << "[" << l << ", " << r << "] cnt = " << cnt << " val = " << val << endl;
if(l < r) {
left->dbg();
right->dbg();
}
}
};
node *tree;
int curS;
void solve(vector<ii> &at, vector<ll> &dp, vector<ll> &opt, int L, int R, int oL, int oR) {
//cerr << "Solving [" << L << ", " << R << "] [" << oL << ", " << oR << "]" << endl;
if(L > R)
return;
int m = (L + R) / 2;
ll cur = -1;
int cut = 0;
for(int rest = oL; rest <= min(oR, m); rest++) {
//cerr << curS << " " << rest << endl;
while(curS < rest) {
curS++;
//cerr << "Adding " << curS << endl;
tree->upd(at[curS].first, at[curS].second);
}
while(curS > rest) {
//cerr << "Removing " << curS << endl;
tree->upd(at[curS].first, -1);
curS--;
}
//cerr << "Tree at " << rest << endl;
//tree->dbg();
//cerr << "Querying tree " << rest << endl;
ll res = tree->bsum(m - rest);
if(res > cur) {
cur = res;
cut = rest;
}
}
dp[m] = cur;
opt[m] = cut;
solve(at, dp, opt, L, m - 1, oL, cut);
solve(at, dp, opt, m + 1, R, cut, oR);
}
void extreme(vector<ll> &at, vector<ll> &dp, vector<ll> &opt) {
int n = at.size();
dp.resize(2*n);
opt.resize(2*n);
vector<ii> pas(n);
for(int i = 0; i < n; i++)
pas[i] = {at[i], i};
sort(pas.begin(), pas.end());
//for(int i = 0; i < n; i++)
// cerr << pas[i].first << " " << pas[i].second << endl;
vector<ii> comp(n);
for(int i = 0; i < n; i++)
comp[pas[i].second] = ii{i, pas[i].first};
//for(int i = 0; i < n; i++)
// cerr << comp[i].first << " " << comp[i].second << endl;
tree = new node(0, n - 1);
curS = -1;
solve(comp, dp, opt, 0, 2*n - 1, 0, n - 1);
delete tree;
//cerr << "SOLVED" << endl;
//for(int i = 0; i < 2*n; i++) {
// cerr << i << " " << dp[i] << " " << opt[i] << endl;
//}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if(start == 0) {
vector<ll> dp, opt, at;
at.resize(n);
for(int i = 0; i < n; i++)
at[i] = attraction[i];
extreme(at, dp, opt);
return dp[min(d, 2*n - 1)];
}
if(start == n - 1) {
vector<ll> dp, opt, at;
at.resize(n);
for(int i = n - 1; i >= 0; i--)
at[i] = attraction[n - 1 - i];
extreme(at, dp, opt);
return dp[min(d, 2*n - 1)];
}
// Right then left, then left then right
ll ans = 0;
for(int it = 0; it < 2; it++) {
vector<ll> ri, dpr, optr, le, dpl, optl;
for(int i = start; i < n; i++)
ri.push_back(attraction[i]);
for(int i = start - 1; i >= 0; i--)
le.push_back(attraction[i]);
extreme(ri, dpr, optr);
extreme(le, dpl, optl);
/*cerr << "Right" << endl;
for(int i = 0; i < dpr.size(); i++)
cerr << i << " " << dpr[i] << " " << optr[i] << endl;
cerr << "Left" << endl;
for(int i = 0; i < dpl.size(); i++)
cerr << i << " " << dpl[i] << " " << optl[i] << endl;*/
for(int sri = 0; sri <= min((int)dpr.size() - 1, d); sri++) {
int trav = optr[sri];
ans = max(ans, dpr[sri]);
if(sri + trav + 1 > d)
continue;
ans = max(ans, dpr[sri] + dpl[min(d - sri - trav - 1, (int)dpl.size() - 1)]);
}
reverse(attraction, attraction + n);
start = n - 1 - start;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
624 ms |
17216 KB |
Output is correct |
| 2 |
Correct |
603 ms |
17272 KB |
Output is correct |
| 3 |
Correct |
627 ms |
17272 KB |
Output is correct |
| 4 |
Correct |
612 ms |
17276 KB |
Output is correct |
| 5 |
Correct |
964 ms |
15864 KB |
Output is correct |
| 6 |
Correct |
227 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
479 ms |
9080 KB |
Output is correct |
| 8 |
Correct |
613 ms |
10872 KB |
Output is correct |
| 9 |
Correct |
153 ms |
3712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
768 KB |
Output is correct |
| 2 |
Correct |
10 ms |
896 KB |
Output is correct |
| 3 |
Correct |
10 ms |
896 KB |
Output is correct |
| 4 |
Correct |
22 ms |
788 KB |
Output is correct |
| 5 |
Correct |
20 ms |
800 KB |
Output is correct |
| 6 |
Correct |
7 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
512 KB |
Output is correct |
| 8 |
Correct |
6 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
620 ms |
17272 KB |
Output is correct |
| 2 |
Correct |
679 ms |
18168 KB |
Output is correct |
| 3 |
Correct |
793 ms |
6724 KB |
Output is correct |
| 4 |
Correct |
21 ms |
640 KB |
Output is correct |
| 5 |
Correct |
6 ms |
512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
384 KB |
Output is correct |
| 7 |
Correct |
6 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2142 ms |
11992 KB |
Output is correct |
| 9 |
Correct |
2142 ms |
12044 KB |
Output is correct |
