Submission #139964

#	Time	Username	Problem	Language	Result	Execution time	Memory
139964		evpipis	Holiday (IOI14_holiday)	C++11	100 / 100	1264 ms	13684 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;
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
*/

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