Submission #697316

#	Time	Username	Problem	Language	Result	Execution time	Memory
697316		vjudge1	Holiday (IOI14_holiday)	C++17	100 / 100	953 ms	30096 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{
	struct node{
		LL sz,sm;
	}a[N<<2];
	int rk[N];
	void build(int l,int r,int rt){
		if(l==r){
			rk[l]=rt;
			return ;
		}
		int mid=l+r>>1;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
	}
	void clear(){
//		printf("CLEAR\n");
		build(1,m,1);
		memset(a,0,sizeof(a));
	}
	void upd(int rt,int x){
		while(rt)a[rt].sz++,a[rt].sm+=b[x],rt>>=1;
	}
	LL query(int l,int r,int rt,int k){
		if(a[rt].sz<=k)return a[rt].sm;
		if(l==r)return b[l]*k;
		int mid=l+r>>1;
		if(a[rt<<1|1].sz<k)return query(l,mid,rt<<1,k-a[rt<<1|1].sz)+a[rt<<1|1].sm;
		return query(mid+1,r,rt<<1|1,k);
	}
	void insert(int x){
//		printf("INSERT %d\n",x);
		int pos=lower_bound(b+1,b+m+1,x)-b;
		upd(rk[pos],pos);
	}
	LL qry(int k){
		if(k<=0)return 0;
		auto res=query(1,m,1,k);
//		printf("query %d %lld\n",k,res);
		return res;
	}
}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 'void KthTree::build(int, int, int)':
holiday.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid=l+r>>1;
      |           ~^~
holiday.cpp: In member function 'long long int KthTree::query(int, int, int, int)':
holiday.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid=l+r>>1;
      |           ~^~
holiday.cpp: In function 'std::vector<long long int> solve(std::vector<int>, int, int, int)':
holiday.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |    LL mid=l1+r1>>1,val=-1,pos=0;
      |           ~~^~~

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