Submission #849285

#	Time	Username	Problem	Language	Result	Execution time	Memory
849285		Hakiers	Holiday (IOI14_holiday)	C++17	100 / 100	255 ms	9508 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
const int BASE = 1 << 17;
pair<int, int> atrac[BASE];
long long dp[BASE];
long long dp2[BASE];
int globD;
long long res = 0;
struct Node{
	long long sum;
	int count; 
};
Node TREE[BASE << 1];

void update(int v, int sum){
 	v+= BASE;
	if(sum < 0)
		TREE[v].count = 0;
	else TREE[v].count = 1;
		
	TREE[v].sum += sum;
	
	v/=2;
	
	while(v > 0){
		int l = 2*v, r = 2*v + 1;
		TREE[v].count = TREE[l].count + TREE[r].count;
		TREE[v].sum = TREE[l].sum + TREE[r].sum;
		v/=2;
	}
}

long long find(int v, int a, int b, int val){
	if(TREE[v].count == 0 || val <= 0) return 0;
	else if(TREE[v].count <= val)
		return TREE[v].sum;
	else{
		int l = 2*v, r = 2*v + 1, mid = (a+b)/2;;
		
		if(TREE[r].count >= val) return find(r, mid+1, b, val);
		return TREE[r].sum + find(l, a, mid, val - TREE[r].count);
	}

}
int L = 0, R = -1;

void mo(int a, int b){
	while(L > a){
		L--;
		update(atrac[L].second, atrac[L].first);
	}
	while(R < b){
		R++;
		update(atrac[R].second, atrac[R].first);
		
	}
	while(L < a){
		update(atrac[L].second, -atrac[L].first);
		L++;
		
	}
	while(R > b){
		update(atrac[R].second, -atrac[R].first);
		R--;
	}
			
}

void dpc(int l, int r, int optl, int optr, int start){
	int mid = (l+r)/2;
	if(r < l) return;
	
	mo(optl, mid);
	int opt = optl;
	for(int i = optl; i <= min(mid, optr) && i <= start; i++){
		
		int cost = (start - i) + (mid - i);
		//cout << mid << " " << i << " " << cost << endl;
		if(globD - cost > 0){
			long long earn = find(1, 0, BASE-1, globD - cost);
			//cout << mid << " " << i << " " << earn << endl;
			if(dp[mid] <= earn){
				dp[mid] = earn;
				res = max(res, earn);
				opt = i;
			}
		}
		update(atrac[i].second, -atrac[i].first);
		++L;
	}
	
	dpc(l, mid-1, optl, opt, start);
	dpc(mid+1, r, opt, optr, start);

}

void dpc2(int l, int r, int optl, int optr, int start){
	int mid = (l+r)/2;
	if(r < l) return;
	
	mo(mid, optr);
	int opt = optr;
	
	for(int i = optr; i >= max(mid, optl) && i >= start; i--){
		
		int cost = (i - start) + (i - mid);
		if(globD - cost > 0){
			long long earn = find(1, 0, BASE-1, globD - cost);
			if(dp2[mid] <= earn){
				dp2[mid] = earn;
				res = max(res, earn);
				opt = i;
			}
		}
		update(atrac[i].second, -atrac[i].first);
		--R;
	}
	
	dpc2(l, mid-1, optl, opt, start);
	dpc2(mid+1, r, opt, optr, start);

}	


long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
/*int main(){
	int n, start, d;
	vector<int> attraction;
	cin >> n >> start >> d;
	for(int i = 0; i < n; i++){
		int xd;
		cin >> xd;
		attraction.push_back(xd);
	}
	*/
	
	
	vector<pair<int, int>> pos;
	for(int i = 0; i < n; i++)
		pos.push_back({attraction[i], i});
	
	sort(pos.begin(), pos.end());
	
	for(int id = 0; id < n; id++)
		atrac[pos[id].second] = {pos[id].first, id};
	
	
	globD = d;
	dpc(start, n-1, 0, n-1, start);
	dpc2(0, start, 0, n-1, start);
	
	
		
	
    	//cout << res << endl;
    	return res;
}

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