Submission #134641

#	Time	Username	Problem	Language	Result	Execution time	Memory
134641		mirbek01	Holiday (IOI14_holiday)	C++11	100 / 100	259 ms	49520 KiB

holiday

#include "holiday.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

struct st{
	int l, r, cnt;
	long long sum;
	st(){
		l = r = cnt = sum = 0;
	}
}t[N * 20];

int d, start, sz;
long long ans;
vector <int> vec;
int root[N], cn;

void upd(int ov, int v, int pos, int tl = 0, int tr = sz){
	if(tl == tr){
		t[v].sum = t[ov].sum + vec[tl];
		t[v].cnt = t[ov].cnt + 1;
	} else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm){
			if(!t[v].l) t[v].l = ++ cn;
			t[v].r = t[ov].r;
			upd(t[ov].l, t[v].l, pos, tl, tm);
		} else{
			if(!t[v].r) t[v].r = ++ cn;
			t[v].l = t[ov].l;
			upd(t[ov].r, t[v].r, pos, tm + 1, tr);
		}
		t[v].cnt = t[ t[v].l ].cnt + t[ t[v].r ].cnt;
		t[v].sum = t[ t[v].l ].sum + t[ t[v].r ].sum;   
	}
}

long long get(int ov, int v, int cnt, int tl = 0, int tr = sz){
	if(cnt <= 0) return 0ll;
	if(tl == tr){
		long long k = min(t[v].cnt - t[ov].cnt, cnt);
		return k * 1ll * vec[tl];
	}
	int tm = (tl + tr) >> 1;
	int k = t[ t[v].r ].cnt - t[ t[ov].r ].cnt;
	if(k <= cnt)
		return t[ t[v].r ].sum - t[ t[ov].r ].sum + get(t[ov].l, t[v].l, cnt - k, tl, tm);
	return get(t[ov].r, t[v].r, cnt, tm + 1, tr);
}

void calc(int l, int r, int opl, int opr){
	if(l > r) return ;
	int md = (l + r) >> 1, opt = -1;
	long long ret = -1;
	for(int i = opl; i <= opr; i ++){
		int lenA = (start - md), lenB = (i - start);
		int cnt = d - lenA - lenB - min(lenA, lenB);
		long long now = get(root[md], root[i + 1], cnt);
		if(ret < now){
			ret = now;
			opt = i;
		}
	}
	ans = max(ans, ret);
	calc(l, md - 1, opl, opt);
	calc(md + 1, r, opt, opr);
}

long long int findMaxAttraction(int n, int startS, int D, int ar[]) {
	d = D;
	start = startS;
	vec.push_back(-2e9);
	for(int i = 0; i < n; i ++){
		vec.push_back(ar[i]);
	}
	sort(vec.begin(),vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	sz = (int)vec.size() - 1;
	for(int i = 0; i < n; i ++){
		ar[i] = lower_bound(vec.begin(),vec.end(), ar[i])-vec.begin();
	}
	for(int i = 1; i <= n; i ++){
		root[i] = ++ cn;
		upd(root[i - 1], root[i], ar[i - 1]);
	}
	calc(0, start, start, n);
	return ans;
}

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