Submission #432146

#	Time	Username	Problem	Language	Result	Execution time	Memory
432146		dreezy	Holiday (IOI14_holiday)	C++17	47 / 100	5078 ms	8320 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define ll long long
#define pill pair<int,ll>
#define pi pair<int,int>
#define f first
#define s second
/***********************/
struct SegTree{
	vector<pill> st;
	int sz;
	SegTree(int n){
		sz = n;
		st.assign(n*4, {0,0ll});
	}
	
	
	void updactive(int n, int l, int r, int ind, int val){
		if(l == r){
			st[n].f = val;
			return;
		}
		
		int mid = (l + r)/2;
		
		if(mid >= ind)
			updactive(2*n+1, l, mid, ind, val);
		else
			updactive(2*n + 2, mid + 1, r, ind, val);
		st[n].f = st[2*n+1].f + st[2*n+2].f;
	}
	
	void updval(int n, int l, int r, int ind, int val){
		if(l == r){
			st[n].s = val;
			return;
		}
		
		int mid = (l + r)/2;
		
		if(mid >= ind)
			updval(2*n+1, l, mid, ind, val);
		else
			updval(2*n + 2, mid + 1, r, ind, val);
		st[n].s = st[2*n+1].s + st[2*n+2].s;
	}
	

	void activate(int city,int val){
		updactive(0,0,sz, city, 1);
		updval(0,0,sz, city, val);
	}
	
	void deactivate(int city){
		updactive(0,0,sz, city, 0);
		updval(0,0,sz, city, 0);
	}
	
	int getfirst(int n, int l, int r, int val){
		if(l == r) return l;
		int mid = (l + r)/2;
		
		if(st[2*n+1].f >= val )
			return getfirst(2*n+1, l, mid, val);
		return getfirst(2*n+ 2, mid + 1, r, val - st[2*n+1].f);
	}
	
	int getfirst(int val){
		int target = st[0].f - val +1;
		if(target <=0)
			return 0;
		return getfirst(0, 0, sz, target);
	}
	
	
	ll qrysum(int n, int l, int r, int s, int e){
		if(s<= l and e >= r)	return st[n].s;
		
		ll ans = 0;
		int mid = (l + r)/2;
		
		if( mid >= s)
			ans += qrysum(2*n+1, l, mid, s, e);
		if(mid < e)
			ans+=qrysum(2*n+2, mid + 1, r, s,e);
		return ans;
	}
	
	ll getlargest(int rng){
		if(rng <= 0) return 0;
		int lower = getfirst(rng);
		//cout << lower<<endl;
		return qrysum(0, 0,sz, lower, sz );
		
	}

	
};



long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	ll ans = 0;
	
	
	//spend right days travelling
	//visit day - right cities
	
	vector<pi> cities(n);
	for(int i =0; i<n; i++){
		cities[i] = {attraction[i], i};
	}
	
	sort(cities.begin(), cities.end());
	

		
	vector<int> inds(n);
	for(int i= 0; i<n;i++)
		inds[cities[i].s] = i;
	

	
	
	for(int left = start; left >= 0; left--){
		SegTree st(n);
		for(int i = left; i<start; i++){
			st.activate(inds[i], attraction[i]);
			
		}
		
		for(int right = start; right <n; right++){
			st.activate(inds[right], attraction[right]);
			
			int dist = right - left + min(start - left, right - start);
			if(d - dist <= 0) break;
			

			//cout << left << ", "<<right<< ": "<<dist<<", "<<cursum<<endl;
			ans = max(ans, st.getlargest(d - dist));
		}
	}
	
    return ans;
}

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