Submission #1244972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244972		dpsaveslives	Nile (IOI24_nile)	C++20	100 / 100	74 ms	11592 KiB

nile

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int fa[N],mn[N],mn2[N][2],sz[N],n,q,tot;
struct node{
	int w,a,b;
}p[N],ask[N],dlt[N<<1];
bool cmp(node a,node b){return a.w==b.w?a.b>b.b:a.w<b.w;}
ll res;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int p1,int p2)
{
	if(p2==0)
	{
		int f=find(p1);
		if(sz[f]&1)res-=min(mn[f],mn2[f][f&1]);
		mn[f]=min(mn[f],p[p1].a-p[p1].b);
		if(sz[f]&1)res+=min(mn[f],mn2[f][f&1]);
	}
	else
	{
		int f1=find(p1),f2=find(p2);
		if(sz[f1]&1)res-=min(mn[f1],mn2[f1][f1&1]);
		if(sz[f2]&1)res-=min(mn[f2],mn2[f2][f2&1]);
		fa[f2]=f1;
		sz[f1]+=sz[f2];
		mn[f1]=min(mn[f1],mn[f2]);
		mn2[f1][0]=min(mn2[f1][0],mn2[f2][0]);
		mn2[f1][1]=min(mn2[f1][1],mn2[f2][1]);
		if(sz[f1]&1)res+=min(mn[f1],mn2[f1][f1&1]);
	}
	return;
}
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();
	vector<ll>ans;
 	for(int i=1;i<=n;i++)p[i]={W[i-1],A[i-1],B[i-1]};
 	sort(p+1,p+n+1,cmp);
 	q=E.size();
 	for(int i=0;i<q;i++) ask[i+1]={E[i],i};
 	sort(ask+1,ask+q+1,cmp);
 	ans.resize(q);
 	for(int i=2;i<=n;i++) dlt[++tot]={p[i].w-p[i-1].w,i-1,i};
	for(int i=2;i<n;i++) dlt[++tot]={p[i+1].w-p[i-1].w,i,0};
	sort(dlt+1,dlt+tot+1,cmp);
	for(int i=1;i<=n+1;i++)
	{
		fa[i]=i;
		mn[i]=1e9;
		mn2[i][i&1]=p[i].a-p[i].b;
		mn2[i][(i&1)^1]=1e9;
		sz[i]=1;
	}
	for(int i=1;i<=n;i++) res+=p[i].a;
	for(int i=1,p=0;i<=q;i++)
	{
		while(p<tot&&dlt[p+1].w<=ask[i].w)
			p++, add(dlt[p].a,dlt[p].b);
		ans[ask[i].a]=res;
	}
 	return ans;
}

• 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