Submission #139379

#	Time	Username	Problem	Language	Result	Execution time	Memory
139379		evpipis	Holiday (IOI14_holiday)	C++14	Compilation error	0 ms	0 KiB

holiday

//#define TEST

#ifndef TEST
#include "grader.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, mx = 1e9;
int arr[len], n, st, dur;

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[len];

pnode update(pnode t, int l, int r, int i){
    if (l == r)
        return new node(t->sum+i, t->cnt+1, null, null);

    int mid = (l+r)/2;
    if (i <= mid)
        return new node(t->sum+i, t->cnt+1, update(t->lef, l, mid, i), t->rig);
    return new node(t->sum+i, t->cnt+1, t->lef, update(t->rig, mid+1, r, i));
}

ll query(pnode a, pnode b, int l, int r, int k){
    //printf("l = %d, r = %d, k = %d\n", l, r, k);
    if (l == r)
        return l*1LL*k;

    int mid = (l+r)/2, rcnt = a->rig->cnt - b->rig->cnt;
    ll rsum = a->rig->sum - b->rig->sum;

    //printf("mid = %d, rcnt = %d, rsum = %lld\n", mid, rcnt, rsum);
    if (rcnt >= k)
        return query(a->rig, b->rig, mid+1, r, k);
    return query(a->lef, b->lef, l, mid, k-rcnt) + rsum;
}

ll solve(int l, int r, int o1, int o2){
    if (l > r)
        return 0;

    int mid = (l+r)/2, rem = dur-2*(mid-st)-(st-o2), opt;
    ll ans = -1, sum = 0;

    if (rem <= 0)
        return solve(l, mid-1, o1, o2);

    //printf("find answer for mid = %d, rem = %d\n", mid, rem);
    for (int j = o2; j >= o1 && rem > 0; j--){
        ll cur = query(root[mid], root[j-1], 0, mx, min(rem, mid-j+1));

        if (cur > ans)
            ans = cur, opt = j;

        rem--;
    }

    //printf("l = %d, r = %d, o1 = %d, o2 = %d\n", l, r, o1, o2);
    //printf("ans = %lld, opt = %d\n", ans, opt);

    ans = max(ans, solve(l, mid-1, o1, opt));
    ans = max(ans, solve(mid+1, r, opt, o2));

    return ans;
}

ll findMaxAttraction(int N, int ST, int D, int att[]){
    n = N, st = ST+1, dur = D;
    for (int i = 1; i <= n; i++)
        arr[i] = att[i-1];

    null->lef = null->rig = null;

    root[0] = null;
    for (int i = 1; i <= n; i++)
        root[i] = update(root[i-1], 0, mx, arr[i]);
    ll ans = solve(st, n, 1, st);

    reverse(arr+1, arr+1+n);
    st = n-st+1;

    root[0] = null;
    for (int i = 1; i <= n; i++)
        root[i] = update(root[i-1], 0, mx, arr[i]);
    ans = max(ans, solve(st, n, 1, st));

    return ans;
}

#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
*/

Compilation message (stderr)

holiday.cpp:4:10: fatal error: grader.h: No such file or directory
 #include "grader.h"
          ^~~~~~~~~~
compilation terminated.