Submission #1129931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129931		StefanSebez	Nile (IOI24_nile)	C++20	100 / 100	101 ms	12016 KiB

nile

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,inf=1e9;
ll ans;
int n,q,C[N];
int par[N],mn[N][3],sajz[N];
void Init(){
	for(int i=0;i<n;i++){
		par[i]=i;
		mn[i][0]=C[i];
		sajz[i]=1;
		mn[i][1]=mn[i][2]=inf;
	}
}
int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);}
void US(int u,int v){
	u=FS(u),v=FS(v);
	if(u==v) return;
	par[v]=u;
	int bit=sajz[u]&1;
	mn[u][0]=min(mn[u][0],mn[v][bit]);
	mn[u][1]=min(mn[u][1],mn[v][bit^1]);
	mn[u][2]=min(mn[u][2],mn[v][2]);
	sajz[u]+=sajz[v];
}
int MIN(int u){u=FS(u);if(sajz[u]&1) return min(mn[u][0],mn[u][2]);return 0;}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,std::vector<int> B, std::vector<int> E){
	n=W.size(),q=E.size();
	array<int,3>nesto[n+10];
	for(int i=0;i<n;i++) nesto[i]={W[i],A[i],B[i]};
	sort(nesto,nesto+n);
	for(int i=0;i<n;i++) W[i]=nesto[i][0],A[i]=nesto[i][1],B[i]=nesto[i][2];
	//for(int i=0;i<n;i++) printf("%i %i %i\n",W[i],A[i],B[i]);
	for(int i=0;i<n;i++) C[i]=A[i]-B[i];
	vector<array<int,3>>ev;
	for(int i=0;i<n;i++){
		if(i>=1) ev.pb({W[i]-W[i-1],i-1,i});
		if(i>=2) ev.pb({W[i]-W[i-2],i-2,i});
	}
	sort(ev.begin(),ev.end());
	//for(auto i:ev) printf("%i %i %i\n",i[0],i[1],i[2]);
	vector<pair<int,int>>Qs;
	vector<ll>res(q);
	for(int i=0;i<q;i++)Qs.pb({E[i],i});
	sort(Qs.begin(),Qs.end());
	for(int i=0;i<n;i++) ans+=A[i];
	Init();
	for(int I=0,j=0;I<q;I++){
		int d=Qs[I].fi;
		while(j<ev.size()&&ev[j][0]<=d){
			int u=ev[j][1],v=ev[j][2];
			if(u+1==v){
				ans-=MIN(u)+MIN(v);
				US(u,v);
				ans+=MIN(u);
			}
			else{
				int x=u+1,rt=FS(x);
				ans-=MIN(rt);
				mn[rt][2]=min(mn[rt][2],C[x]);
				ans+=MIN(rt);
			}
			//printf("%i: ",j);for(int i=0;i<n;i++) printf("%i ",MIN(i));printf("\n");
			j++;
		}
		res[Qs[I].se]=ans;
	}
	return res;
}

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