oj.uz

Submission #7441

# Submission time Handle Problem Language Result Execution time Memory
7441 2014-08-05T18:42:31 Z ainta Holiday (IOI14_holiday) C++
0 / 100
 364 ms 6628 KB 
#include"holiday.h"
#include<algorithm>
using namespace std;
#define SZ 131072
#define N_ 100010
long long Res;
struct A{
	int a, num;
	bool operator <(const A &p)const{
		return a < p.a;
	}
}ord[N_];
struct ST{
	long long Sum;
	int C;
}IT[SZ*2+2];
int num[N_], N;
void Ins(int node, int b, int e, int x, int ck){
	if (b == e){
		if (ck == IT[node].C)return;
		if (ck){
			IT[node].C = 1;
			IT[node].Sum = ord[b].a;
		}
		else{
			IT[node].C = 0, IT[node].Sum = 0;
		}
		return;
	}
	int m = (b + e) >> 1;
	if (x <= m)Ins(node * 2, b, m, x, ck);
	else Ins(node * 2 + 1, m + 1, e, x, ck);
	IT[node].Sum = IT[node * 2].Sum + IT[node * 2 + 1].Sum;
	IT[node].C = IT[node * 2].C + IT[node * 2 + 1].C;
}
long long Gap(int node, int x){
	if (IT[node].C <= x)return IT[node].Sum;
	if (IT[node * 2 + 1].C >= x) return Gap(node * 2 + 1, x);
	else return IT[node * 2 + 1].Sum + Gap(node * 2, x - IT[node * 2 + 1].C);
}
void DP(int st, int b, int e, int s, int l, int d){
	if (b > e)return;
	int m = (b + e) >> 1, i, t, x;
	long long M = 0, S;
	for (i = m; i <= e; i++)
		Ins(1, 1, SZ, num[i], 1);
	for (i = s; i <= l; i++){
		Ins(1, 1, SZ, num[i], 1);
		t = d - st - i + m + m;
		if (t <= 0)break;
		S = Gap(1, t);
		if (M < S){
			M = S, x = i;
		}
	}
	if (Res < M)Res = M;
	for (i = s; i <= l; i++)Ins(1, 1, SZ, num[i], 0);
	DP(st, b, m - 1, s, x, d);
	for (i = m; i <= e; i++)Ins(1, 1, SZ, num[i], 0);
	for (i = s; i < x; i++)Ins(1, 1, SZ, num[i], 1);
	DP(st, m + 1, e, x, l, d);
	for (i = s; i < x; i++)Ins(1, 1, SZ, num[i], 0);
}
void Do(int st, int d){
	int i;
	DP(st, max(0, st - (d-1)/2), st, st, N - 1, d);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	int i;
	N = n;
	for (i = 0; i < n; i++){
		ord[i].a = attraction[i];
		ord[i].num = i;
	}
	sort(ord, ord + n);
	for (i = 0; i < n; i++)num[ord[i].num] = i;
	Do(start, d);
	for (i = 0; i < n; i++)num[n - 1 - ord[i].num] = i;
	Do(n - 1 - start, d);
	return Res;
}

Subtask #1
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 6624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 364 ms 6628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 364 ms 6620 KB Output isn't correct
2 Halted 0 ms 0 KB -