oj.uz

답안 #298055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298055 2020-09-12T10:27:30 Z Plurm 휴가 (IOI14_holiday) C++11
100 / 100
 472 ms 57324 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int* attraction;
int start;
int n,d;
vector<pair<int,int> > vatr;
long long pseg[8000005];
int cseg[8000005];
int lb[8000005];
int rb[8000005];
int llink[8000005];
int rlink[8000005];
int nodesz;
int newnode(int old = -1){
	int nn = ++nodesz;
	if(old != -1){
		pseg[nn] = pseg[old];
		cseg[nn] = cseg[old];
		lb[nn] = lb[old];
		rb[nn] = rb[old];
		llink[nn] = llink[old];
		rlink[nn] = rlink[old];
	}
	return nn;
}
int build(int l, int r){
	int c = newnode();
	pseg[c] = 0;
	cseg[c] = 0;
	lb[c] = l;
	rb[c] = r;
	if(l == r) return c;
	int k = (l+r)/2;
	llink[c] = build(l, k);
	rlink[c] = build(k+1, r);
	return c;
}
int update(int o, int idx){
	int c = newnode(o);
	if(lb[o] == rb[o]){
		cseg[c] = 1;
		pseg[c] = vatr[idx].first;
		return c;
	}
	int k = (lb[o] + rb[o])/2;
	if(idx <= k){
		llink[c] = update(llink[c], idx);
	}else{
		rlink[c] = update(rlink[c], idx);
	}
	pseg[c] = pseg[llink[c]] + pseg[rlink[c]];
	cseg[c] = cseg[llink[c]] + cseg[rlink[c]];
	return c;
}
long long query(int n1, int n2, int lim){
	int avail = cseg[n2] - cseg[n1];
	if(avail <= lim) return pseg[n2] - pseg[n1];
	int rsz = cseg[rlink[n2]] - cseg[rlink[n1]];
	if(rsz < lim){
		return query(llink[n1], llink[n2], lim - rsz) + pseg[rlink[n2]] - pseg[rlink[n1]];
	}else{
		return query(rlink[n1], rlink[n2], lim);
	}
}
vector<int> versions;
long long computeManyMax(int k, int l, int r){
	long long res = query(versions[l], versions[r+1], k);
	return res;
}
long long divideConquer(int l, int r, int ll, int rr){
	if(l > r) return 0ll;
	int m = (l+r)/2;
	long long ans = 0;
	int rmidx = -1;
	int lmidx = -1;
	for(int i = ll; i <= rr; i++){
		int dist = m-i+min(start-i,m-start);
		if(dist > d) continue;
		long long cur = computeManyMax(d - dist, i, m);
		if(cur > ans){
			ans = cur;
			lmidx = rmidx = i;
		}else if(cur == ans){
			rmidx = i;
		}
	}
	ans = max(ans, divideConquer(l, m-1, ll, rmidx));
	ans = max(ans, divideConquer(m+1, r, lmidx, rr));
	return ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	::attraction = attraction;
	::start = start;
	::n = n;
	::d = d;
	for(int i = 0; i < n; i++) vatr.emplace_back(attraction[i], i);
	sort(vatr.begin(), vatr.end());
	int root = build(0, n-1);
	versions.push_back(root);
	for(int i = 0; i < n; i++){
		int idx = lower_bound(vatr.begin(), vatr.end(), make_pair(attraction[i], i)) - vatr.begin();
		int newroot = update(root, idx);
		versions.push_back(newroot);
		root = newroot;
	}
	return divideConquer(start, n-1, 0, start);
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 56712 KB Output is correct
2 Correct 81 ms 56556 KB Output is correct
3 Correct 89 ms 56556 KB Output is correct
4 Correct 88 ms 56560 KB Output is correct
5 Correct 128 ms 51656 KB Output is correct
6 Correct 32 ms 14964 KB Output is correct
7 Correct 64 ms 27760 KB Output is correct
8 Correct 83 ms 33904 KB Output is correct
9 Correct 24 ms 10364 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1664 KB Output is correct
2 Correct 3 ms 1664 KB Output is correct
3 Correct 3 ms 1664 KB Output is correct
4 Correct 4 ms 1536 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 57196 KB Output is correct
2 Correct 97 ms 57324 KB Output is correct
3 Correct 113 ms 24560 KB Output is correct
4 Correct 4 ms 1536 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 472 ms 57192 KB Output is correct
9 Correct 386 ms 57196 KB Output is correct