Submission #204484

#	Time	Username	Problem	Language	Result	Execution time	Memory
204484		junodeveloper	절취선 (JOI14_ho_t5)	C++14	100 / 100	369 ms	20508 KiB

2014_ho_t5

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repr(i,a,b) for(int i=(a);i>=(b);i--)
#ifdef LOCAL
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) 1
#endif
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
struct vert {
	int x,y1,y2;
	bool operator<(const vert& b)const{
		return x<b.x;
	}
};
struct hori {
	int y,x1,x2;
	bool operator<(const hori& b)const{
		return y<b.y;
	}
};
struct event {
	int t,x,i;
	bool operator<(const event& b)const{
		return x==b.x?t<b.t:x<b.x;
	}
};
struct SegTree {
	const int INF=1e9;
	int n;
	vector<int> sum,mn,mx;
	void init(int _n){
		n=_n;
		sum=vi(4*n,0);
		mn=vi(4*n,INF);
		mx=vi(4*n,-1);
	}
	void update(int p,int x,int tl,int tr,int h) {
		if(tl>tr||tr<p||p<tl)return;
		if(tl==tr) {
			if(x==-1)sum[h]=0,mn[h]=INF,mx[h]=-1;
			else sum[h]=1,mn[h]=mx[h]=x;
			return;
		}
		int mid=(tl+tr)/2;
		update(p,x,tl,mid,h*2);
		update(p,x,mid+1,tr,h*2+1);
		sum[h]=sum[h*2]+sum[h*2+1];
		mn[h]=min(mn[h*2],mn[h*2+1]);
		mx[h]=max(mx[h*2],mx[h*2+1]);
	}
	pip query(int l,int r,int tl,int tr,int h) {
		if(l>r||tl>tr||tr<l||r<tl)return make_pair(0,make_pair(INF,-1));
		if(l<=tl&&tr<=r)return make_pair(sum[h],make_pair(mn[h],mx[h]));
		int mid=(tl+tr)/2;
		pip ql=query(l,r,tl,mid,h*2);
		pip qr=query(l,r,mid+1,tr,h*2+1);
		return make_pair(ql.fi+qr.fi,make_pair(min(ql.se.fi,qr.se.fi),max(ql.se.se,qr.se.se)));
	}
	void update(int p,int x){update(p,x,0,n-1,1);}
	pip query(int l,int r){return query(l,r,0,n-1,1);}
	void dbg() {
		//debug("st: ");
		//for(int i=0;i<n;i++)debug("%d ",query(i,i).se.fi);puts("");
	}
}st;
int w,h,n;
vector<vert> va;
vector<hori> vb;
vector<event> ve;
vector<int> vx,vy;
vector<int> par;
vector<bool> chk;
vector<vector<int>> lst;
int pn(int u){return u==par[u]?u:(par[u]=pn(par[u]));}
void us(int a,int b){
	a=pn(a),b=pn(b);
	if(a==b)return;
	if(sz(lst[a])<sz(lst[b]))swap(a,b);
	for(auto& it:lst[b]) {
		//debug("a:%d,b:%d,it:%d,chk:%d\n",a,b,it,(int)chk[it]);
		if(chk[it])st.update(vb[it].y,a);
		lst[a].pb(it);
	}
	par[b]=a;
}
ll solve() {
	int i;
	par=vi(sz(vb));
	chk=vector<bool>(sz(vb),false);
	lst=vector<vector<int>>(sz(vb));
	st.init(sz(vy));
	for(i=0;i<sz(vb);i++) {
		par[i]=i;
		lst[i].pb(i);
	}
	ve.clear();
	for(i=0;i<sz(va);i++)ve.pb({1,va[i].x,i});
	for(i=0;i<sz(vb);i++) {
		ve.pb({0,vb[i].x1,i});
		ve.pb({2,vb[i].x2,i});
	}
	sort(all(ve));
	ll V=sz(va)+sz(vb),E=0,C=0;
	for(auto& e:ve) {
		if(e.t==0) {
			//debug("add %d\n",e.i);
			chk[e.i]=true;
			st.update(vb[e.i].y,pn(e.i));
		} else if(e.t==1) {
			pip r=st.query(va[e.i].y1,va[e.i].y2);
			E+=r.fi;
			if(r.fi==0) {
				C++;
				continue;
			}
			int dbg=0;
			while(1) {
				//debug("* %d %d %d %d\n",r.se.fi,r.se.se,va[e.i].y1,va[e.i].y2);
				if(r.se.fi==r.se.se)break;
				us(r.se.fi,r.se.se);
				r=st.query(va[e.i].y1,va[e.i].y2);
			}
		} else {
			//debug("remove %d\n",e.i);
			chk[e.i]=false;
			st.update(vb[e.i].y,-1);
		}
	}
	fill(all(chk),false);
	for(i=0;i<sz(vb);i++)chk[pn(i)]=true;
	for(i=0;i<sz(vb);i++)if(chk[i])C++;
	//debug("C:%lld,%lld\n",C,E);
	return C-V+E;
}
inline int comp(vector<int>& v,int x){return lower_bound(all(v),x)-v.begin();}
void add_line(int x1,int y1,int x2,int y2) {
	if(x1>x2)swap(x1,x2);
	if(y1>y2)swap(y1,y2);
	if(x1==x2){ 
		va.pb({x1,y1,y2});
		vx.pb(x1);vy.pb(y1);vy.pb(y2);
	} else { 
		vb.pb({y1,x1,x2});
		vx.pb(x1);vx.pb(x2);vy.pb(y1);
	}
}
int main() {
	int i;
	scanf("%d%d%d",&w,&h,&n);
	for(i=1;i<=n;i++) {
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		add_line(x1,y1,x2,y2);
	}
	add_line(0,0,w,0);
	add_line(w,0,w,h);
	add_line(w,h,0,h);
	add_line(0,h,0,0);
	sort(all(vx));vx.erase(unique(all(vx)),vx.end());
	sort(all(vy));vy.erase(unique(all(vy)),vy.end());
	for(auto& it:va) {
		it.x=comp(vx,it.x);
		it.y1=comp(vy,it.y1);
		it.y2=comp(vy,it.y2);
	}
	for(auto& it:vb) {
		it.x1=comp(vx,it.x1);
		it.x2=comp(vx,it.x2);
		it.y=comp(vy,it.y);
	}
	printf("%lld",solve());
	return 0;
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'll solve()':
2014_ho_t5.cpp:133:8: warning: unused variable 'dbg' [-Wunused-variable]
    int dbg=0;
        ^~~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:166:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&w,&h,&n);
  ~~~~~^~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50