Submission #62640

#	Time	Username	Problem	Language	Result	Execution time	Memory
62640		evpipis	Holiday (IOI14_holiday)	C++11	0 / 100	2849 ms	66560 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;

//#define TEST

#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 n, st;
ll out[3*len];

struct node{
    ll sum;
    int cnt;
    node *left, *right;

    node(ll s, int c, node *l, node *r){
        sum = s;
        cnt = c;
        left = l;
        right = r;
    }

    node *ins(int l, int r, int i);
};

node *root[len], *null = new node(0, 0, NULL, NULL);

node *node::ins(int l, int r, int i){
    if (l == r)
        return new node(sum+i, cnt+1, null, null);

    int mid = (l+r)/2;
    if (i <= mid)
        return new node(sum+i, cnt+1, left->ins(l, mid, i), right);
    return new node(sum+i, cnt+1, left, right->ins(mid+1, r, i));
}

ll query(node *a, node *b, int l, int r, int k){
    if (l == r)
        return k*1LL*l;

    int mid = (l+r)/2, com = b->right->cnt - a->right->cnt;
    ll add = b->right->sum - a->right->sum;

    if (k <= com)
        return query(a->right, b->right, mid+1, r, k);
    return add + query(a->left, b->left, l, mid, k-com);
}

ll ask(int l, int r, int k){
    return query(root[l-1], root[r], 1, mx, k);
}

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

    int mid = (l+r)/2, pos;
    for (int i = o1; i <= o2; i++){
        int k = min(i-st+1, mid-i+st);
        ll cur = ask(st, i, k);
        if (cur > out[mid])
            out[mid] = cur, pos = i;
    }

    solve(l, mid-1, o1, pos);
    solve(mid+1, r, pos, o2);
}

ll findMaxAttraction(int N, int ST, int d, int attraction[]){
    n = N, st = ST + 1;
    root[0] = null->left = null->right = null;
    for (int i = 1; i <= n; i++)
        root[i] = root[i-1]->ins(1, mx, attraction[i-1]);

    //for (int i = 1; i <= n; i++)
      //  for (int j = i+1; j <= n; j++)
        //    printf("(%d, %d) = %lld\n", i, j, ask(i, j, 2));

    for (int i = 0; i <= d; i++)
        out[i] = -1;
    solve(0, d, st, n);
    return out[d];
}

#ifdef TEST
int main() {
    int N, start, d;
    int attraction[100000];
    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
*/

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:72:10: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
     solve(l, mid-1, o1, pos);
     ~~~~~^~~~~~~~~~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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