Submission #139391

#	Time	Username	Problem	Language	Result	Execution time	Memory
139391		evpipis	Holiday (IOI14_holiday)	C++11	0 / 100	127 ms	65540 KiB

holiday

//#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, mx = 1e9;
int arr[len], n, st, dur;
stack<pair<ii, ii> > stk;

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 sl, int sr, int so1, int so2){
    ll fin = 0;

    stk.push(mp(mp(sl, sr), mp(so1, so2)));
    while (!stk.empty()){
        int l = stk.top().fi.fi, r = stk.top().fi.se, o1 = stk.top().se.fi, o2 = stk.top().se.se;
        stk.pop();

        if (l > r)
            continue;

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

        if (rem <= 0)
            continue;

        //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);

        stk.push(mp(mp(l, mid-1), mp(o1, opt)));
        stk.push(mp(mp(mid+1, r), mp(opt, o2)));

        fin = max(ans, fin);
    }

    return fin;
}

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: In function 'll solve(int, int, int, int)':
holiday.cpp:73:22: warning: unused variable 'sum' [-Wunused-variable]
         ll ans = -1, sum = 0;
                      ^~~
holiday.cpp:92:20: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
         stk.push(mp(mp(mid+1, r), mp(opt, o2)));
                    ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53