Submission #1157073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157073		_rain_	Garden (JOI23_garden)	C++20	100 / 100	2532 ms	16316 KiB

garden

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)500000;
const int INF=(int)1e9;

class Disjoint_Set_Union{
	public:
		vector<int>par,sz;
		void init(int _n)
		{
			par.assign(_n+2,0) , sz.assign(_n+2,1);
			iota(par.begin(),par.end(),0);
		}
		int Find(int u){
			return par[u]==u?par[u]:par[u]=Find(par[u]);
		}
		void unite(int u,int v){
			u=Find(u),v=Find(v);
			if (u==v) return;
			if (sz[u]<sz[v]) swap(u,v);
			par[v]=u,sz[u]+=sz[v];
		}
		int getsz(int x){
			return sz[Find(x)];
		}
};

Disjoint_Set_Union dsu;

vector<int>f;
vector<int>need_change[N+2];
int n,m,d,gap;
int need_x[2][N+2],r[N+2];
bool del[N+2]={};

int Find(vector<int>&f,int x){
	return lower_bound(f.begin(),f.end(),x)-f.begin()-1;
}

void insert(int x,bool w){
	for(auto&k : {-1,1}){
		int nxt=(x+d+k)%d;
		if (del[nxt]) dsu.unite(x,nxt);
		gap=max(gap,(int)dsu.getsz(x));
	}
	del[x]=true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin>>n>>m>>d;
	LL ans=(LL)1e18;
	for(int i=1;i<=n;++i) {
		int x,y; cin>>x>>y;
		f.push_back(x),f.push_back(x+d);
		r[y]=INF;
	}
	sort(f.begin(),f.end()); f.resize(unique(f.begin(),f.end())-f.begin());
	for(int i=1;i<=m;++i){
		int x,y; cin>>x>>y;
		r[y]=max(r[y],x);
		need_change[x].push_back(y);
	}
	for(int i=0;i<d;++i){
		if (i){
			for(auto&x:need_change[i-1]){
				r[x]=max(r[x],(i-1)+d);
			}
		}
		
		dsu.init(d);
		
		vector<pair<int,int>>v;
		for(int j=0;j<d;++j) v.push_back({r[j]-i+1,j});
		sort(v.begin(),v.end());
		
		int height=f[Find(f,i+d)]-i+1;
		assert(f[Find(f,i+d)]<=i+d);
		
		gap=0;
		ans=min(ans,(LL)height*d);
		for(int j=0;j<d;++j) del[j]=false;
		for(int j=0;j<d;++j){
			height=max(height,v[j].first);
			if (height>d) break;
			int x=v[j].second;
			insert(x,i==4);
			ans=min(ans,(LL)height*(d-gap));
		}
	}
	
	cout<<ans;
	
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25