Submission #432672

#	Time	Username	Problem	Language	Result	Execution time	Memory
432672		dreezy	Holiday (IOI14_holiday)	C++17	100 / 100	1664 ms	38340 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
#define mp make_pair
/***********************/
struct SegTree{
	vector<pill> st;
	vector<int> minmax;
	int sz;

	void init(int n, bool right){
		sz = n;
		st.assign(n*4, {0,0ll});
		if(right)
			minmax.assign(n*4, 0);
		else
			minmax.assign(n*4, 1e9);
		
	}
	
	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 updmin(int n, int l, int r, int ind, int val){
		if(l == r){
			minmax[n] = val;
			return;
		} 
		
		int mid = (l + r)/2;
		
		if(mid >= ind)
			updmin(2*n + 1, l, mid, ind , val);
		else
			updmin(2*n+2, mid + 1, r, ind , val);
		minmax[n] = min(minmax[2* n +1], minmax[2*n + 2]);
	
	}
	
	void updmax(int n, int l, int r, int ind, int val){
		if(l == r){
			minmax[n] = val;
			return;
		} 
		
		int mid = (l + r)/2;
		
		if(mid >= ind)
			updmax(2*n + 1, l, mid, ind , val);
		else
			updmax(2*n+2, mid + 1, r, ind , val);
		minmax[n] = max(minmax[2* n +1], minmax[2*n + 2]);
	
	}
	

	void activate(int ind,int city, int val, bool right){
		updactive(0,0,sz, ind, 1);
		updval(0,0,sz, ind, val);
		
		
		if(right)
			updmax(0,0,sz,ind,city);
		else
			updmin(0,0,sz,ind, city);
	}

	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;
	}
	
	int getmin(int n, int l, int r, int s, int e){
		if(s<= l and e >= r)	return minmax[n];
		
		int ans = 1e9;
		int mid = (l + r)/2;
		
		if( mid >= s)
			ans = min(getmin(2*n+1, l, mid, s, e), ans);
		if(mid < e)
			ans = min(getmin(2*n+2, mid + 1, r, s,e), ans);
		return ans;
	}
	
	int getmax(int n, int l, int r, int s, int e){
		if(s<= l and e >= r)	return minmax[n];
		
		int ans = -1;
		int mid = (l + r)/2;
		
		if( mid >= s)
			ans = max(getmax(2*n+1, l, mid, s, e), ans);
		if(mid < e)
			ans = max(getmax(2*n+2, mid + 1, r, s,e),ans);
		return ans;
	}
	
	pair<ll, int>  getlargest(int rng, bool right){
		int lower = getfirst(rng);
		//cout << lower<<endl;
		ll res = qrysum(0, 0,sz, lower, sz );
		if(right)
			return {res, getmax(0, 0,sz, lower,sz)};
		return {res, getmin(0, 0,sz, lower,sz)};
		
	}
	

	
};


vector<int> inds;
int n;
int start;

vector<ll> dpright;
vector<int> minright;
vector<int> attraction;
SegTree stright;
vector<int> lvlactive;
int cnt = 0;
void dcright(int s_, int e_, int l_, int r_, int lvl_){
	cnt = 0;
	priority_queue<pair<pair<int,int>,tuple<int,int,int,int,int>>> pq;
	
	pq.push({{-lvl_,cnt--},{s_, e_, l_, r_,lvl_} });
	int curlevel = -1;
	while(pq.size()){
		int st, e, l, r, lvl;
		tie(st, e,l,r,lvl) = pq.top().s;
		pq.pop();
		if(e < st || l > r) continue;
		if(lvl > curlevel){
			curlevel = lvl;
			stright.init(n,true);
		}
		//cout <<lvl<<", "<<lvlactive[lvl]<< ": "<< st<<", "<<e<<": "<<l<<", "<<r<<endl;
		for(int i = lvlactive[lvl]; i < l; i++)
			stright.activate(inds[i],i, attraction[i], true);
		lvlactive[lvl] = l -1;
		int days = (st + e)/2;
		for(int right = l; right <=r; right++){
			stright.activate(inds[right],right, attraction[right], true);
			int dist = right - start;
			if(days - dist < 0){
				break;
			}
			pair<ll, int> res = stright.getlargest(days - dist, true);
			if(days - dist == 0) res.s = right;
			//if(days == 2) cout << res.f<<", "<<res.s<<", "<<dist<<endl;
			if(res.f > dpright[days]){
				dpright[days] = res.f;
				minright[days] = res.s;
			}
			else if(res.f == dpright[days]){
				minright[days] = min(minright[days], res.s);
			}
			lvlactive[lvl] = right;
		}
		
		pq.push({{-(lvl +1), cnt--},{st, days -1, l, minright[days], lvl+1}});
		pq.push({{-(lvl+1), cnt--}, {days+1, e, minright[days], r, lvl+1}});
		
	}
	
	


	
	//dcright(s, days -1, l, minright[days], lvl+1);
		//dcright(days +1, e, minright[days], r,lvl+1);
}


vector<ll> dpleft;
vector<int> maxleft;
SegTree stleft;
void dcleft(int s_, int e_, int l_, int r_, int lvl_){
	cnt = 0;


	
	//cout << maxleft[days]<<", "<<dpleft[days]<<endl;

	
	priority_queue<pair<pair<int,int>,tuple<int,int,int,int,int>>> pq;
	
	pq.push({{-lvl_,cnt--},{s_, e_, l_, r_,lvl_} });
	int curlevel = -1;
	while(pq.size()){
		int st, e, l, r, lvl;
		tie(st, e,l,r,lvl) = pq.top().s;
		pq.pop();
		if(e < st || l > r) continue;
		if(lvl > curlevel){
			curlevel = lvl;
			stleft.init(n,false);
			
		}
		//cout <<lvl<<", "<<lvlactive[lvl]<< ": "<< st<<", "<<e<<": "<<l<<", "<<r<<endl;
	
		for(int i = lvlactive[lvl]; i > r; i--)
		stleft.activate(inds[i],i, attraction[i], false);

		int days = (st + e)/2;
		for(int left = r; left >=l; left--){
			stleft.activate(inds[left],left, attraction[left], false);
			int dist = start - left;
			
			if(days - dist < 0) break;
			pair<ll, int> res = stleft.getlargest(days - dist,false);
			if(days - dist == 0) res.s = left;
			//if(days == 4) cout << dist<<"!"<<res.f<<endl;
			//if(e == 1) cout << dist<<", "<<res<endl;
			if(res.f > dpleft[days]){
				dpleft[days] = res.f;
				maxleft[days] = res.s;
			}
			else if(res.f == dpleft[days]){
				maxleft[days] = max(maxleft[days], res.s);
			}
			lvlactive[lvl] = left;
		}
		
		pq.push({{-(lvl +1), cnt--},{st, days -1, maxleft[days],r, lvl+1}});
		pq.push({{-(lvl+1), cnt--}, {days+1, e, l, maxleft[days], lvl+1}});
		
		
		//dcleft(s, days -1, maxleft[days],r, lvl+1);
		//dcleft(days +1, e,l, maxleft[days],lvl+1);
	}
	
}

long long int findMaxAttraction(int n_, int start_, int d, int attractions[]) {
	n = n_;
	start = start_;
	attraction.assign(n,0);
	
	for(int i =0; i<n; i++) attraction[i] = attractions[i];
	vector<pi> cities(n);
	for(int i =0; i<n; i++){
		cities[i] = {attraction[i], i};
	}
	
	sort(cities.begin(), cities.end());
	

		
	inds.assign(n, 0);
	
	for(int i= 0; i<n;i++)
		inds[cities[i].s] = i;
	dpright.assign(d+1, 0);
	minright.assign(d + 1, 1e9);
	lvlactive.assign(30,start);
	dcright(1, d, start, n -1, 0);

	dpleft.assign(d+1, 0);
	maxleft.assign(d + 1, 0);
	lvlactive.assign(30,start-1);
	dcleft(1, d,0, start-1, 0);

	ll ans = 0;

	for(int daysright = 0; daysright <= d; daysright++){
		int distright = daysright == 0 ? 0: minright[daysright] - start;
		int daysleft = max(0,d - daysright - distright);
		//cout<< daysleft<<", "<<daysright<<", "<<distright<<": "<<dpleft[daysleft]<<", "<<dpright[daysright]<<endl;
		ans = max(ans,dpleft[daysleft] + dpright[daysright] );
	}
	
	//cout <<endl;
	for(int daysleft = 0; daysleft <= d; daysleft++){
		int distleft = daysleft == 0 ? 0: start - maxleft[daysleft] ;
		int daysright = max(0,d - daysleft - distleft);
		//cout<< daysleft<<", "<<daysright<<", "<<maxleft[daysleft]<<": "<<dpleft[daysleft]<<", "<<endl;
		//cout << dpright.size()<<": "<<dpright[daysright]<<endl;
		ans = max(ans,dpleft[daysleft] + dpright[daysright] );
	}


    return ans;
}

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