Submission #706282

#	Time	Username	Problem	Language	Result	Execution time	Memory
706282		jamezzz	Holiday (IOI14_holiday)	C++17	30 / 100	370 ms	6644 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(x) x.begin(),x.end()
typedef long long ll;

#define maxn 100005

int n,s,d,a[maxn],cantake,lptr,rptr;
ll pfx[maxn],ans,sm;
multiset<ll> in,out;

void fix(){
	while(in.size()>cantake){
		auto it=in.begin();
		sm-=*it;
		out.insert(*it);
		in.erase(it);
	}
	while(in.size()<cantake&&!out.empty()){
		auto it=--out.end();
		sm+=*it;
		in.insert(*it);
		out.erase(it);
	}
}

void add(int x){
	sm+=x;
	in.insert(x);
	fix();
}

void rem(int x){
	if(out.find(x)!=out.end()){
		out.erase(out.find(x));
	}
	else{
		in.erase(in.find(x));
		sm-=x;
		fix();
	}
}

void dnc(int l,int r,int optl,int optr){
	if(l>r)return;
	int m=(l+r)>>1;
	while(lptr<m)rem(a[lptr++]);
	while(m<lptr)add(a[--lptr]);
	while(rptr<optl-1)add(a[++rptr]);
	while(optl-1<rptr)rem(a[rptr--]);
	ll mx=0,best=0;
	for(int i=optl;i<=optr;++i){
		add(a[i]);
		cantake=max(d-(s-m+i-m),0);
		fix();
		if(sm>=mx)best=i,mx=sm;
	}
	rptr=optr;
	ans=max(ans,mx);
	dnc(l,m-1,optl,best);
	dnc(m+1,r,best,optr);
}

void solve(){
	in.clear();out.clear();
	sm=cantake=0;
	lptr=1,rptr=s;
	for(int i=s;i>=1;--i){
		add(a[i]);
		cantake=max(d-(s-i),0);
		fix();
		ans=max(ans,sm);
	}
	dnc(1,s-1,s,n);
}

ll findMaxAttraction(int _n,int _s,int _d,int _a[]){
	n=_n,s=_s+1,d=_d;
	for(int i=1;i<=n;++i)a[i]=_a[i-1];
	solve();
	for(int i=1;i<=n/2;++i)swap(a[i],a[n-i+1]);
	s=n-s+1;
	solve();
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void fix()':
holiday.cpp:16:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |  while(in.size()>cantake){
      |        ~~~~~~~~~^~~~~~~~
holiday.cpp:22:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |  while(in.size()<cantake&&!out.empty()){
      |        ~~~~~~~~~^~~~~~~~

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