Submission #849024

#	Time	Username	Problem	Language	Result	Execution time	Memory
849024		Hakiers	Holiday (IOI14_holiday)	C++17	0 / 100	54 ms	8656 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) 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);
	}

}
int l = 0, r = 0;

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


void dpc(int l, int r, int optl, int optr, int start){
	int mid = (l+r)/2;
	if(mid < start || 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);
		if(globD - cost > 0){
			long long earn = find(1, 0, BASE-1, globD - cost);
			if(dp[mid] <= earn){
				dp[mid] = earn;
				res = max(res, earn);
				opt = i;
			}
		}
		update(atrac[i].second, -atrac[i].first);
	}
	
	dpc(l, mid, 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(mid > start || 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);
	}
	
	dpc2(l, mid, 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);
	
	
		
	
    	// << res << endl;
    	return res;
}

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