Submission #139405

#	Time	Username	Problem	Language	Result	Execution time	Memory
139405		evpipis	Holiday (IOI14_holiday)	C++11	24 / 100	136 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], where[len], n, st, dur;
stack<pair<ii, ii> > stk;
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[len];

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

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

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 a->sum - b->sum;

    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, opt = -1;
        ll ans = -1;

        //printf("find answer for mid = %d, rem = %d\n", mid, rem);
        for (int j = o2; j >= o1; j--){
            int rem = dur - (mid-j + min(mid-st, st-j));

            if (rem <= 0)
                break;

            ll cur = query(root[mid], root[j-1], 1, n, min(rem, mid-j+1));

            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)
            stk.push(mp(mp(l, mid-1), mp(o1, o2)));
        else{
            stk.push(mp(mp(l, mid-1), mp(o1, opt)));
            stk.push(mp(mp(mid+1, r), mp(opt, o2)));
        }
    }

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

    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;

    root[0] = null->lef = null->rig = null;
    for (int i = 1; i <= n; i++)
        root[i] = update(root[i-1], 1, n, where[i], arr[i]);
    return solve(st, n, 1, st);
}

#ifdef TEST

int attraction[100005];

int main() {
    freopen("sample-1.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
*/

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