Submission #1178171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178171		alexander707070	Nile (IOI24_nile)	C++20	0 / 100	173 ms	3912 KiB

nile

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long inf=1e17;

struct item{
	int w;
	int a,b;

	inline friend bool operator < (item fr,item sc){
		return fr.w<sc.w;
	}
};

int delta;
int n;
item a[MAXN];
vector< pair<int,int> > raz,qs;
long long ans[MAXN];

struct Segment_Tree{
	struct node{
		int len;
		long long ans[3][3];
		
		void fills(int x){
			for(int i=0;i<3;i++){
				for(int f=0;f<3;f++){
					ans[i][f]=x;
				}
			}
		}

		long long mins(int l,int r){			
			long long res=inf;

			for(int i=l;i<3;i++){
				for(int f=r;f<3;f++){
					res=min(res,ans[i][f]);
				}
			}

			return res;
		}
	};

	node tree[4*MAXN];

	node combine(vector<item> mids,node fr,node sc,int lsz,int rsz,int l,int r){
		node res;

		res.len=fr.len+sc.len;

		long long sum=0;
		for(auto s:mids){
			sum+=s.a;
		}

		if(r-l+1>=4){
			for(int i=0;i<3;i++){
				for(int f=0;f<3;f++){
					res.ans[i][f]=fr.mins(i,0) + sc.mins(0,f);
					if(abs(mids[0].w-mids[1].w)<=delta)res.ans[i][f]=min(res.ans[i][f] , fr.mins(i,1) + sc.mins(1,f) - mids[0].a-mids[1].a+mids[0].b+mids[1].b);
					if(abs(mids[2].w-mids[1].w)<=delta)res.ans[i][f]=min(res.ans[i][f] , fr.mins(i,2) + sc.mins(1,f) - mids[2].a-mids[1].a+mids[2].b+mids[1].b);
					if(abs(mids[0].w-mids[3].w)<=delta)res.ans[i][f]=min(res.ans[i][f] , fr.mins(i,1) + sc.mins(2,f) - mids[0].a-mids[3].a+mids[0].b+mids[3].b);
				}
			}

		}else{
			for(int i=0;i<3;i++){
				for(int f=0;f<3;f++){
					if(i+f>res.len){
						res.ans[i][f]=inf;
						continue;
					}

					res.ans[i][f]=sum;

					for(int t=l+i;t<=r-f;t++){
						for(int k=t+1;k<=r-f;k++){
							if(abs(a[k].w-a[t].w)<=delta)res.ans[i][f]=min(res.ans[i][f],sum-a[k].a-a[t].a+a[k].b+a[t].b);
						}
					}

				}
			}
		}

		return res;
	}

	void update(int v,int l,int r,int pos){
		if(l==r){
			tree[v].len=1;
			tree[v].fills(a[l].a);
			return;
		}else{
			int tt=(l+r)/2;

			if(pos<=tt)update(2*v,l,tt,pos);
			else update(2*v+1,tt+1,r,pos);

			vector<item> z;

			z.push_back(a[tt]);
			z.push_back(a[tt+1]);
			if(tt-1>=l)z.push_back(a[tt-1]);
			if(tt+2<=r)z.push_back(z[tt+2]);

			tree[v]=combine(z,tree[2*v],tree[2*v+1],tt-l+1,r-tt,l,r);
		}
	}

	void upd(int ind){
		for(int i=max(ind-10,1);i<=min(ind+10,n);i++){
			update(1,1,n,i);
		}
	}
}tree;

vector<long long> calculate_costs(vector<int> W, vector<int> A,vector<int> B,vector<int> E){
	n=int(W.size());

	for(int i=1;i<=n;i++){
		a[i]={W[i-1],A[i-1],B[i-1]};
	}
	sort(a+1,a+n+1);

	delta=0;
	for(int i=1;i<=n;i++)tree.update(1,1,n,i);

	for(int i=1;i<=n;i++){
		if(i+1<=n)raz.push_back({a[i+1].w-a[i].w,i});
		if(i+2<=n)raz.push_back({a[i+2].w-a[i].w,i});
	}

	sort(raz.begin(),raz.end());

	for(int i=0;i<E.size();i++){
		qs.push_back({E[i],i});
	}

	sort(qs.begin(),qs.end());

	int pt=0;
	for(int i=0;i<qs.size();i++){
		delta=qs[i].first;

		while(pt<raz.size() and raz[pt].first<=qs[i].first){
			tree.upd(raz[pt].second);
			pt++;
		}

		ans[qs[i].second]=tree.tree[1].ans[0][0];
	}

	vector<long long> sol;
	for(int i=0;i<qs.size();i++)sol.push_back(ans[i]);

	return sol;
}

/*int main(){

	auto res=calculate_costs({15, 12, 2, 10, 21},
		{5, 4, 5, 6, 3},
		{1, 2, 2, 3, 2},
		{5, 9, 1});

	for(auto s:res)cout<<s<<" ";

	return 0;
}*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18