Submission #30029

#	Time	Username	Problem	Language	Result	Execution time	Memory
30029		Bruteforceman	Holiday (IOI14_holiday)	C++11	100 / 100	1556 ms	18768 KiB

holiday

#include"holiday.h"
#include "bits/stdc++.h"
long long frontR[300010];
long long frontB[300010];
long long backR[300010];
long long backB[300010];
std :: vector <int> P, Q;
std :: vector <int> CP, CQ;
std :: vector <int> RP, RQ;
int t[100010 * 4];
long long sum[100010 * 4];
int N;

bool cmp1(int x, int y) {
	return P[x] < P[y];
}
bool cmp2(int x, int y) {
	return Q[x] < Q[y];
}
void update(int x, long long val, int c = 1, int b = 0, int e = N) {
	if(b == e) {
		t[c] = 1;
		sum[c] = val;
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) update(x, val, l, b, m);
	else update(x, val, r, m+1, e);
	t[c] = t[l] + t[r];
	sum[c] = sum[l] + sum[r];
} 
void del(int x, int c = 1, int b = 0, int e = N) {
	if(b == e) {
		t[c] = sum[c] = 0;
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) del(x, l, b, m);
	else del(x, r, m+1, e);
	t[c] = t[l] + t[r];
	sum[c] = sum[l] + sum[r];
}
long long query(int take, int c = 1, int b = 0, int e = N) {
	if(b == e) {
		if(take > 0) return sum[c];
		else return 0;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(t[r] >= take) return query(take, r, m+1, e);
	else return query(take - t[r], l, b, m) + sum[r];
}

void solveFrontR(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		update(RP[i], P[i]);
		long long o = query(m - (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	for(int i = opt; i <= e; i++) {
		del(RP[i]);
	}
	solveFrontR(m + 1, r, opt, e);
	for(int i = b; i < opt; i++) {
		del(RP[i]);
	}
	solveFrontR(l, m - 1, b, opt);
	frontR[m] = std :: max(frontR[m], best);
}

void solveFrontB(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		update(RP[i], P[i]);
		long long o = query(m - 2 * (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	for(int i = opt; i <= e; i++) {
		del(RP[i]);
	}
	solveFrontB(m + 1, r, opt, e);
	for(int i = b; i < opt; i++) {
		del(RP[i]);
	}
	solveFrontB(l, m - 1, b, opt);
	frontB[m] = std :: max(frontB[m], best);
}

void solveBackR(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		update(RQ[i], Q[i]);
		long long o = query(m - (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	for(int i = opt; i <= e; i++) {
		del(RQ[i]);
	}
	solveBackR(m + 1, r, opt, e);
	for(int i = b; i < opt; i++) {
		del(RQ[i]);
	}
	solveBackR(l, m - 1, b, opt);
	backR[m] = std :: max(backR[m], best);
}
void solveBackB(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		update(RQ[i], Q[i]);
		long long o = query(m - 2 * (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	for(int i = opt; i <= e; i++) {
		del(RQ[i]);
	}
	solveBackB(m + 1, r, opt, e);
	for(int i = b; i < opt; i++) {
		del(RQ[i]);
	}
	solveBackB(l, m - 1, b, opt);
	backB[m] = std :: max(backB[m], best);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	for(int i = 0; i < start; i++) {
		P.push_back(attraction[i]);
	}
	for(int i = start + 1; i < n; i++) {
		Q.push_back(attraction[i]);
	}
	N = n;
	RP.resize(n);
	RQ.resize(n);
	std :: reverse(P.begin(), P.end());
	for(size_t i = 0; i < P.size(); i++) CP.push_back(i);
	for(size_t i = 0; i < Q.size(); i++) CQ.push_back(i);
	std :: sort(CP.begin(), CP.end(), cmp1);
	std :: sort(CQ.begin(), CQ.end(), cmp2);
	for(size_t i = 0; i < CP.size(); i++) RP[CP[i]] = i;
	for(size_t i = 0; i < CQ.size(); i++) RQ[CQ[i]] = i;

	
	if(!P.empty()) {
		solveFrontR(1, d, 0, P.size() - 1);
		solveFrontB(1, d, 0, P.size() - 1);
	}
	if(!Q.empty()) {
		solveBackR(1, d, 0, Q.size() - 1);
		solveBackB(1, d, 0, Q.size() - 1);	
	}
	long long ans = 0;
	for(int i = 0; i < d; i++) {
		ans = std :: max(ans, frontB[i] + attraction[start] + backR[d - i - 1]);
		ans = std :: max(ans, frontR[d - i - 1] + attraction[start] + backB[i]);
	}
	for(int i = 0; i <= d; i++) {
		ans = std :: max(ans, frontB[i] + backR[d - i]);
		ans = std :: max(ans, frontR[d - i] + backB[i]);
	}
    return ans;
}

Compilation message (stderr)

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: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53