Submission #64229

#	Time	Username	Problem	Language	Result	Execution time	Memory
64229		mhnd	Holiday (IOI14_holiday)	C++14	100 / 100	4117 ms	16592 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 3e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

pair<ll,int> a[N];
int p[N],num[4*N],S,n;
ll seg[4*N],d1[N],d2[N];

void update(int n,int s,int e,int in,bool to){
	if(s > in || e < in)return;
	if(s == e){
		num[n] = to;
		seg[n] = 1ll * to * a[in].first;
		return;
	}
	update(n*2,s,(s+e)/2,in,to);
	update(n*2+1,(s+e)/2+1,e,in,to);
	num[n] = num[n*2] + num[n*2+1];
	seg[n] = seg[n*2] + seg[n*2+1];
}

ll get(int n,int rem){
	if(rem <= 0)return 0;
	if(rem >= num[n])return seg[n];
	return get(n*2,rem) + get(n*2+1,rem-num[2*n]);
}

void solve(int l,int r,int x,int y,int at,ll v[],int w){
	if(l > r || x > y)return;
	int cur = (l+r)/2;
	at = -1;
	v[cur] = -1;
	for(int i=x;i<=y;i++){
		update(1,1,n,p[i],1);
		ll ans = get(1,cur - w * abs(i-S));
		if(ans > v[cur]){
			v[cur] = ans;
			at = i;
		}
	}
	for(int i=at;i<=y;i++)update(1,1,n,p[i],0);
	solve(cur+1,r,at,y,-1,v,w);
	for(int i=x;i<=y;i++)update(1,1,n,p[i],0);
	solve(l,cur-1,x,at,-1,v,w);
}

void solve2(int l,int r,int x,int y,int at,ll v[],int w){
	if(l > r || x > y)return;
	int cur = (l+r)/2;
	at = -1;
	v[cur] = -1;
	for(int i=y;i>=x;i--){
		update(1,1,n,p[i],1);
		ll ans = get(1,cur - w * abs(i-S));
		if(ans > v[cur]){
			v[cur] = ans;
			at = i;
		}
	}
	for(int i=x;i<=at;i++)update(1,1,n,p[i],0);
	solve2(cur+1,r,x,at,at,v,w);
	for(int i=x;i<=y;i++)update(1,1,n,p[i],0);
	solve2(l,cur-1,at,y,at,v,w);
}

void clear(){
	for(int i=1;i<=n;i++)update(1,1,n,p[i],0);
}

long long int findMaxAttraction(int N, int start, int d, int att[]){
	S = start+1;
	n = N;
	for(int i=1;i<=n;i++)a[i] = {att[i-1],i};
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	for(int i=1;i<=n;i++)p[a[i].second]=i;
	ll ans = 0;
	solve(1,d,S,n,-1,d1,2);
	clear();
	solve2(1,d,1,S-1,-1,d2,1);
	clear();
	for(int i=0;i<=d;i++)ans = max(ans,d1[i]+d2[d-i]);
	memset(d1,0,sizeof(d1));
	memset(d2,0,sizeof(d2));
	solve(1,d,S+1,n,-1,d1,1);
	clear();
	solve2(1,d,1,S,-1,d2,2);
	clear();
	for(int i=0;i<=d;i++)ans = max(ans,d1[i]+d2[d-i]);
	return ans;
	cout << "WOW" << endl;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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