Submission #732929

#	Time	Username	Problem	Language	Result	Execution time	Memory
732929		myrcella	Holiday (IOI14_holiday)	C++17	0 / 100	339 ms	5772 KiB

holiday

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

set <pii> ss1,ss2;
vector <int> val;

ll ans = 0,curans = 0;
int curl,curr;
int p,w;

void add(int pos) {
	int tmp = val[pos];
	if (!ss1.empty() and tmp>(*(--ss1.end())).fi) ss1.insert({tmp,pos}),curans += tmp;
	else ss2.insert({tmp,pos});
}

void bye(int pos) {
	int tmp = val[pos];
	if (ss1.find(MP(tmp,pos))!=ss1.end()) curans -= tmp, ss1.erase(MP(tmp,pos));
	else ss2.erase(MP(tmp,pos));
}

void modify(int sz) {
	assert(sz>=0);
	while (SZ(ss1)<sz and !ss2.empty()) {
		auto tmp = (*(--ss2.end()));
		ss2.erase(--ss2.end());
		ss1.insert(tmp);
		curans += tmp.fi;
	}
	while (SZ(ss1)>sz) {
		auto tmp = (*ss1.begin());
		ss1.erase(ss1.begin());
		ss2.insert(tmp);
		curans -= tmp.fi;
	}
}

void dnc(int lmin,int lmax,int rl,int rr,int cop,int col,int cor) {
	
	if (lmin>lmax) return;
	int cur = lmin+lmax>>1;
	while (curl>cur) add(--curl);
	while (curl<cur) bye(curl++);
	while (curr>rr) bye(curr--);
	while (curr<rl) add(++curr);
	if (curr!=rl and curr!=rr) while (curr>rl) bye(curr--);
	int opt = -1;
	ll optval = -1;
	int sz = w-(cop*p+col*cur+cor*curr);
	if (curr==rl) {
		while (1) {
			if (sz>=0) {
				modify(sz);
				if (curans > optval) optval = curans,opt = curr;
			}
			if (curr!=rr) add(++curr);
			else break;
			sz-=cor;
		}
	}
	else {
		assert(curr==rr);
		while (1) {
			if (sz>=0) {
				modify(sz);
				if (curans > optval) optval = curans,opt = curr;
			}
			if (curr!=rl) bye(curr--);
			else break;
			sz+=cor;
		}
	}
	assert(opt!=-1);
//	cout<<lmin<<" "<<lmax<<" "<<rl<<" "<<rr<<" "<<opt<<" "<<optval<<endl;
	ans = max(ans,optval);
	if (curr==rl) dnc(lmin,cur-1,rl,opt,cop,col,cor),dnc(cur+1,lmax,opt,rr,cop,col,cor);
	else dnc(cur+1,lmax,opt,rr,cop,col,cor),dnc(lmin,cur-1,rl,opt,cop,col,cor);
}

ll findMaxAttraction(int n,int start,int d,int* attraction) {
	if (d==0) return 0;
	rep(i,0,n) val.pb(attraction[i]);
	p = start,w=d;
	curl = curr = p;
	curans = val[p];
	ss1.insert({val[p],p});
	dnc(max(0,p-d/2),p,p,n-1,1,-2,1);
	curl = curr = p;
	curans = val[p];
	while (!ss2.empty()) ss2.erase(ss2.begin());
	while (!ss1.empty()) ss1.erase(ss1.begin());
	ss1.insert({val[p],p});
	dnc(max(0,p-d),p,p,n-1,-1,-1,2);
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void dnc(int, int, int, int, int, int, int)':
holiday.cpp:62:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int cur = lmin+lmax>>1;
      |            ~~~~^~~~~

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