Submission #98854

#	Time	Username	Problem	Language	Result	Execution time	Memory
98854		figter001	Holiday (IOI14_holiday)	C++14	0 / 100	1260 ms	7732 KiB

holiday

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e5+50;

vector<pair<int,int>> a,b;
int s,n,idx[nax],l,r,cnt[4*nax],k;
ll dp[nax],d,seg[4*nax],val;

ll dis(ll a,ll b){
	if(a > b)swap(a,b);
	if(s >= a && s <= b){
		ll go = min(abs(s-b) , abs(s-a));
		ll go2 = max(abs(s-b) , abs(s-a));
		return go*2 + go2;
	}else{
		ll go = max(abs(s-b) , abs(s-a));
		return go;
	}
}

void update(int n,int s,int e){
	if(s > r || e < l)return;
	if(s == e){
		seg[n] = val;
		cnt[n] = (val > 0);
		return;
	}
	update(n*2,s,(s+e)/2);
	update(n*2+1,(s+e)/2+1,e);
	seg[n] = seg[n*2] + seg[n*2+1];
	cnt[n] = cnt[n*2] + cnt[n*2+1];
}

ll get(int n,int s,int e){
	if(s == e){
		if(k == 0)
			return 0;
		else 
			return seg[n];
	}
	if(k > cnt[n*2]){
		k -= cnt[n*2];
		return seg[n*2] + get(n*2+1,(s+e)/2+1,e);
	}else{
		return get(n*2,(s+e)/2+1,e);
	}
}

void solve(int x,int y,int ox,int oy){
	if(x > y)
		return;
	int md = (x+y)/2;
	int o1 = -1,o2 = -1;
	ll best = -1e18;
	for(int i=max(ox,x);i<=min(oy,y);i++){
		ll rem = d - dis(ox,i);
		l = r = idx[i];
		val = a[i].first;
		update(1,1,n);
		if(rem < 0)continue;
		k = rem;
		ll cur = get(1,1,n);
		if(cur > best){
			best = cur;
			o1 = i;
		}
	}
	for(int i=max(ox,x);i<=min(oy,y);i++){
		l = r = idx[i];
		val = 0;
		update(1,1,n);
	}
	dp[y] = max(dp[y],best);
	best = -1e18;
	for(int i=min(oy,y);i>=max(ox,x);i--){
		ll rem = d - dis(min(oy,y),i);
		l = r = idx[i];
		val = a[i].first;
		update(1,1,n);
		if(rem < 0)continue;
		k = rem;
		ll cur = get(1,1,n);
		// if(x == 0 && y == 4)cout << i << ' ' << cur << ' ' << best << endl;
		if(cur > best){
			best = cur;
			o2 = i;
		}
	}
	for(int i=min(oy,y);i>=max(ox,x);i--){
		l = r = idx[i];
		val = 0;
		update(1,1,n);
	}
	// cout << ox << ' ' << oy << ' ' << x << ' ' << y << ' ' << dp[y] << ' ' << o1 << ' ' << o2 << endl;
	dp[y] = max(best,dp[y]);
	solve(x,md-1,ox,o1);
	solve(md+1,y,o2,oy);
}

long long int findMaxAttraction(int N, int start, int days, int attraction[]) {
	n = N;
	s = start;
	d = days;
	for(int i=0;i<n;i++)
		a.push_back({attraction[i],i});
	b = a;
	sort(b.begin(),b.end());
	reverse(b.begin(),b.end());
	for(int i=0;i<n;i++)
		idx[b[i].second] = i+1;
	solve(0,n-1,0,n-1);
	ll ans = 0;
	// printf("\n");
	for(int i=0;i<n;i++){
		// cout << i << ' ' << dp[i] << endl;
		ans = max(ans,dp[i]);
	}
    return ans;
}

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: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53