ABC361G WA*5
  • 板块题目总版
  • 楼主Disjoint_cat
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/6 21:55
  • 上次更新2024/7/7 08:56:19
查看原帖
ABC361G WA*5
549499
Disjoint_cat楼主2024/7/6 21:55

rt,调了一场。求 hack。做法是并查集,对于每个横坐标维护形成的区间,相邻的就合并。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=200005;
int n;
VI poi[N],ids[N];
int area[N<<1],fa[N<<1],tot;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){if(x||y)dbg(x,y);fa[find(x)]=find(y);}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n;
	for(int i=1,x,y;i<=n;i++)cin>>x>>y,poi[x+1].PB(y);
	for(int i=1;i<=200002;i++)
	{
		sort(ALL(poi[i]));
		for(int j=0;j<=poi[i].size();j++)
		{
			int id=0;
			if(j&&j<poi[i].size())
			{
				if(poi[i][j]-poi[i][j-1]==1){ids[i].PB(-1);continue;}
				ids[i].PB(id=++tot);
				area[tot]=poi[i][j]-poi[i][j-1]-1,fa[tot]=tot;
			}
			int k=j?lower_bound(ALL(poi[i-1]),poi[i][j-1]+2)-poi[i-1].begin():0;
			if(!k&&(id||poi[i-1].empty())){merge(id,0);continue;}
			k=max(0,k-1);
			while(poi[i-1][k]+1<(j==poi[i].size()?INT_MAX:poi[i][j]))
			{
				if(k+1==poi[i-1].size()){merge(id,0);break;}
				if(poi[i-1][k+1]-poi[i-1][k]>1)merge(id,ids[i-1][k]);
				k++;
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=tot;i++)
		if(find(i)!=find(0))ans+=area[i];
	cout<<ans;

	return 0;
}

2024/7/6 21:55
加载中...