제출 #30023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30023		Bruteforceman	휴가 (IOI14_holiday)	C++11	24 / 100	89 ms	65536 KiB

holiday

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

bool cmpP(int x, int y) {
	return P[x] < P[y];
}
bool cmpQ(int x, int y) {
	return Q[x] < Q[y];
}

struct node {
	node *l, *r;
	long long sum;
	int tot;
	node () {
		l = r = NULL;
		sum = 0;
		tot = 0;
	}	
	void merge() {
		sum = 0;
		tot = 0;
		if(l) {
			sum += l -> sum;
			tot += l -> tot;
		}
		if(r) {
			sum += r -> sum;
			tot += r -> tot;
		}
	}
} *t[100010], *s[100010];

typedef node* pnode;

void init(pnode &cur, int b, int e) {
	cur = new node();
	if(b == e) {
		return ;
	}
	int m = (b + e) >> 1;
	init(cur -> l, b, m);
	init(cur -> r, m+1, e);
}

void insert(pnode &cur, pnode &prev, int pos, int cost, int b, int e) {
	cur = new node();
	if(b == e) {
		cur -> tot = 1;
		cur -> sum = cost;
		return ;
	}
	int m = (b + e) >> 1;
	if(pos <= m) {
		cur -> r = prev -> r;
		insert(cur -> l, prev -> l, pos, cost, b, m);
	} else {
		cur -> l = prev -> l;
		insert(cur -> r, prev -> r, pos, cost, m+1, e);
	}
	cur -> merge();
}
long long query(pnode cur, int take, int b, int e) {
	if(b == e) {
		if(take > 0) return cur -> sum;
		else return 0;
	}
	int m = (b + e) >> 1;
	if(cur -> r -> tot >= take) return query(cur -> r, take, m + 1, e);
	else return query(cur -> l, take - (cur -> r -> tot), b, m) + (cur -> r -> sum);
} 
long long sortSumQ(int x, int take) {
	if(take <= 0) return 0;
	x++;
	return query(s[x], take, 1, Q.size());
}
long long sortSumP(int x, int take) {
	if(take <= 0) return 0;
	x++;
	return query(t[x], take, 1, P.size());
}

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++) {
		long long o = sortSumP(i, m - (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveFrontR(l, m - 1, b, opt);
	solveFrontR(m + 1, r, opt, e);
	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++) {
		long long o = sortSumP(i, m - 2 * (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveFrontB(l, m - 1, b, opt);
	solveFrontB(m + 1, r, opt, e);
	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++) {
		long long o = sortSumQ(i, m - (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveBackR(l, m - 1, b, opt);
	solveBackR(m + 1, r, opt, e);
	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++) {
		long long o = sortSumQ(i, m - 2 * (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveBackB(l, m - 1, b, opt);
	solveBackB(m + 1, r, opt, e);
	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]);
	}
	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(), cmpP);
	std :: sort(CQ.begin(), CQ.end(), cmpQ);
	RP.resize(n + 10);
	RQ.resize(n + 10);
	for(size_t i = 0; i < CP.size(); i++) {
		RP[CP[i]] = i + 1;
	}
	for(size_t i = 0; i < CQ.size(); i++) {
		RQ[CQ[i]] = i + 1;
	}
	if(!P.empty()) {
		t[0] = NULL;
		init(t[0], 1, P.size());
		for(int i = 1; i <= P.size(); i++) {
			t[i] = NULL;
			insert(t[i], t[i - 1], RP[i-1], P[i-1], 1, P.size());	
		}
		solveFrontR(1, d, 0, P.size() - 1);
		solveFrontB(1, d, 0, P.size() - 1);
	}
	if(!Q.empty()) {
		s[0] = NULL;
		init(s[0], 1, Q.size());
		for(int i = 1; i <= Q.size(); i++) {
			s[i] = NULL;
			insert(s[i], s[i - 1], RQ[i-1], Q[i-1], 1, Q.size());
		}
		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;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:183:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i <= P.size(); i++) {
                    ^
holiday.cpp:193:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i <= Q.size(); i++) {
                    ^
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: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53