Submission #338819

#	Time	Username	Problem	Language	Result	Execution time	Memory
338819		alishahali1382	Holiday (IOI14_holiday)	C++14	100 / 100	933 ms	10584 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll ans; // :))
int n, start, D, k, u, v, x, y, t, a, b;
int A[MAXN], L, R;

struct Set{
	ll sum, sz;
	int mark[MAXN];
	priority_queue<pii, vector<pii>, greater<pii>> X;
	priority_queue<pii> Y;
	inline void relax(){
		while (X.size() && mark[X.top().second]!=1) X.pop();
		while (Y.size() && mark[Y.top().second]!=2) Y.pop();
	}
	void Add(int i){
		relax();
		int y=-inf, x=inf;
		if (X.size()) x=X.top().first;
		if (Y.size()) y=Y.top().first;
		if (A[i]<=x) mark[i]=2, Y.push({A[i], i});
		else mark[i]=1, X.push({A[i], i}), sum+=A[i], sz++;
	}
	void Rem(int i){
		if (mark[i]==1) sum-=A[i], sz--;
		mark[i]=0;
		relax(); // not necessary
	}
	ll Get(int k){
		if (k<0) return -INF;
		while (sz<k && Y.size()){
			int i=Y.top().second;
			Y.pop();
			if (mark[i]!=2) continue ;
			mark[i]=1;
			X.push({A[i], i});
			sum+=A[i];
			sz++;
		}
		while (sz>k){
			int i=X.top().second;
			X.pop();
			if (mark[i]!=1) continue ;
			mark[i]=2;
			Y.push({A[i], i});
			sum-=A[i];
			sz--;
		}
		return sum;
	}
} S;

inline void Move(int l, int r){
	while (L<l) S.Rem(L++);
	while (r<R) S.Rem(--R);
	while (l<L) S.Add(--L);
	while (R<r) S.Add(R++);
}
void divide(int tl, int tr, int optl, int optr){
	if (tr<tl) return ;
	int mid=(tl+tr)>>1, opt=-1;
	ll res=-INF-1;
	Move(mid, optl);
	for (int i=optl; i<=optr; i++){
		S.Add(R++);
		ll val=S.Get(D-2*(start-mid)-(i-start));
		if (val>res){
			res=val;
			opt=i;
		}
	}/*
	debug2(mid, opt)
	debug(res)
	cerr<<"\n";
	*/
	assert(opt!=-1);
	ans=max(ans, res);
	Move(tr, opt);
	divide(mid+1, tr, opt, optr);
	Move(mid-1, optl);
	divide(tl, mid-1, optl, opt);
}

ll findMaxAttraction(int nn, int starttt, int d, int attraction[]){
	n=nn;
	D=d;
	start=starttt;
	for (int i=0; i<n; i++) A[i]=attraction[i];
	L=R=start;
	divide(0, start, start, n-1);
//	debug(ans)
	
	
//	return ans;
	
	memset(S.mark, 0, sizeof(S.mark));
	S.relax();
	S.sum=S.sz=0;
	
	reverse(A, A+n);
	start=n-1-start;
	L=R=start;
	divide(0, start, start, n-1);
	
	return ans;
}
/*
5 2 7
10 2 20 30 1

5 2 7
1 30 20 2 10


*/

Compilation message (stderr)

holiday.cpp: In member function 'void Set::Add(int)':
holiday.cpp:41:7: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   41 |   int y=-inf, x=inf;
      |       ^

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