| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 139962 | evpipis | Holiday (IOI14_holiday) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define TEST
#ifndef TEST
#include "holiday.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
const int len = 1e5+5;
int arr[len], where[len], n, st, dur, pol, por;
queue<pair<ii, ii> > myq;
vector<ii> vec;
struct node{
ll sum;
int cnt;
node *lef, *rig;
node(ll s = 0, int c = 0, node *l = NULL, node *r = NULL){
sum = s;
cnt = c;
lef = l;
rig = r;
}
};
typedef node* pnode;
pnode null = new node(), root;
pnode update(pnode t, int l, int r, int i, int s, int c){
pnode cur = t;
if (cur == null)
cur = new node(0, 0, null, null);
cur->sum += s;
cur->cnt += c;
if (l == r)
return cur;
int mid = (l+r)/2;
if (i <= mid)
cur->lef = update(cur->lef, l, mid, i, s, c);
else
cur->rig = update(cur->rig, mid+1, r, i, s, c);
return cur;
}
ll query(pnode t, int l, int r, int k){
if (l == r)
return t->sum;
int mid = (l+r)/2, rcnt = t->rig->cnt;
ll rsum = t->rig->sum;
if (rcnt >= k)
return query(t->rig, mid+1, r, k);
return query(t->lef, l, mid, k-rcnt) + rsum;
}
ll ask(int l, int r, int k){
while (por < r)
por++, root = update(root, 1, n, where[por], arr[por], 1);
while (pol > l)
pol--, root = update(root, 1, n, where[pol], arr[pol], 1);
while (por > r)
root = update(root, 1, n, where[por], -arr[por], -1), por--;
while (pol < l)
root = update(root, 1, n, where[pol], -arr[pol], -1), pol++;
return query(root, 1, n, k);
}
ll solve(int sl, int sr, int so1, int so2){
ll fin = 0;
myq.push(mp(mp(sl, sr), mp(so1, so2)));
while (!myq.empty()){
int l = myq.front().fi.fi, r = myq.front().fi.se, o1 = myq.front().se.fi, o2 = myq.front().se.se;
myq.pop();
if (l > r)
continue;
int mid = (l+r)/2, opt = -1;
ll ans = -1;
//printf("l = %d, r = %d, o1 = %d, o2 = %d\n", l, r, o1, o2);
//printf("find answer for mid = %d\n", mid);
for (int j = o1; j <= o2; j++){
int rem = dur - (mid-j + min(mid-st, st-j));
if (rem <= 0)
continue;
ll cur = ask(j, mid, min(rem, mid-j+1));
//printf("j = %d, mid = %d, cur = %lld\n", j, mid, cur);
if (cur > ans)
ans = cur, opt = j;
}
//printf("l = %d, r = %d, o1 = %d, o2 = %d\n", l, r, o1, o2);
//printf("ans = %lld, opt = %d\n", ans, opt);
fin = max(ans, fin);
if (opt == -1)
myq.push(mp(mp(l, mid-1), mp(o1, o2)));
else{
myq.push(mp(mp(l, mid-1), mp(o1, opt)));
myq.push(mp(mp(mid+1, r), mp(opt, o2)));
}
}
return fin;
}
ll findMaxAttraction(int N, int ST, int D, int att[]){
root = null->lef = null->rig = null;
n = N, st = ST+1, dur = D;
for (int i = 1; i <= n; i++)
arr[i] = att[i-1];
for (int i = 1; i <= n; i++)
vec.pb(mp(arr[i], i));
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i++)
where[vec[i].se] = i+1;
pol = 1;
por = 0;
return solve(st, n, 1, st);
}
#ifdef TEST
int attraction[100005];
int main() {
freopen("sample-4.in", "r", stdin);
int N, start, d;
int i, n_s;
n_s = scanf("%d %d %d", &N, &start, &d);
for (i = 0 ; i < N; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(N, start, d, attraction));
return 0;
}
#endif
/*
5 0 6
10 2 20 30 1
11 0 11
3 2 1 5 6 4 2 3 7 1 5
*/