Submission #697317

#	Time	Username	Problem	Language	Result	Execution time	Memory
697317		vjudge1	Holiday (IOI14_holiday)	C++17	24 / 100	5075 ms	15152 KiB

holiday

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

using namespace std;
void read(int &x){
	x=0;char ch=getchar();int f=1;
	while((ch<'0'||ch>'9')&&ch!=45)ch=getchar();
	if(ch==45)ch=getchar(),f=-1;
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
	x*=f;
}
template<typename T1,typename T2>void cmax(T1 &x,const T2 &y){if(y>x)x=y;}
template<typename T1,typename T2>void cmin(T1 &x,const T2 &y){if(y<x)x=y;}
const int N=3e5+10;
int m;
int b[N];
LL ans[N];
struct KthTree{
	multiset<int> s1,s2;
	LL sum;
	void clear(){
		sum=0;s1.clear(),s2.clear();
	}
	void insert(int x){
		sum+=x;
		s1.insert(x);
	}
	LL qry(int k){
		while(s1.size()<k&&!s2.empty()){
			sum+=*s2.rbegin();
			s1.insert(*s2.rbegin());
			s2.erase(s2.find(*s2.rbegin()));
		}
		while(!s1.empty()&&(int)s1.size()>k){
			sum-=*s1.begin();
			s2.insert(*s1.begin());
			s1.erase(s1.begin());
		}
		return sum;
	}
}T;
vector<LL> solve(vector<int> a,int d,int c,int ex=0){
	memset(ans,0,sizeof(ans));
	queue<tuple<int,int,int,int>> q1,q2;
	q2.push(make_tuple(1,d,1,a.size()-1));	
	while(!q2.empty()){
		swap(q1,q2);T.clear();
		int p=-1;
		while(!q1.empty()){
			auto [l1,r1,l2,r2]=q1.front();q1.pop();
			LL mid=l1+r1>>1,val=-1,pos=0;
			auto upd=[&](int x){
				LL res=T.qry(mid-c*(x+ex));
				if(res>val)val=res,pos=x;
			};
			upd(p);
			while(p+1<=r2){
				T.insert(a[++p]);
				upd(p);
			}
			ans[mid]=val;
			if(mid-1>=l1)q2.push(make_tuple(l1,mid-1,l2,pos));
			if(r1>=mid+1)q2.push(make_tuple(mid+1,r1,pos,r2));
		}
	}
	return vector<LL>(ans,ans+d+1);
}
LL findMaxAttraction(int n,int start,int d,int w[]){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//freopen(".in","w",stdout);
	int i;
	LL ans=0;
//	read(n),read(start),read(d);
	vector<int> a;
	a.resize(n);
	for(i=0;i<n;i++)b[i+1]=a[i]=w[i];
	sort(b+1,b+1+n);m=unique(b+1,b+n+1)-b-1;
	for(int o=0;o<=1;o++){
		auto f=solve(vector<int>(a.begin()+start,a.end()),d,o?1:2);
		vector<int> w(a.begin(),a.begin()+start);
		reverse(w.begin(),w.end());
		auto g=solve(w,d,o?2:1,1);
		for(i=0;i<=d;i++)cmax(ans,f[i]+g[d-i]);
	}
	return ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'long long int KthTree::qry(int)':
holiday.cpp:30:18: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |   while(s1.size()<k&&!s2.empty()){
      |         ~~~~~~~~~^~
holiday.cpp: In function 'std::vector<long long int> solve(std::vector<int>, int, int, int)':
holiday.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |    LL mid=l1+r1>>1,val=-1,pos=0;
      |           ~~^~~

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