Submission #333371

#	Time	Username	Problem	Language	Result	Execution time	Memory
333371		arnold518	절취선 (JOI14_ho_t5)	C++14	10 / 100	3093 ms	248576 KiB

2014_ho_t5

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
const int MAXV = 3.6e6;
 
struct Line
{
	int x1, y1, x2, y2, p;
};
 
int W, H, N, M, SX, SY;
Line A[MAXN+10], B[MAXN+10];
 
vector<int> xcomp, ycomp;
 
ll V, E, C=1;
 
struct BIT
{
	int tree[MAXN+10];
	void update(int i, int x) { for(; i<=SY; i+=(i&-i)) tree[i]+=x; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
	int query(int l, int r) { return query(r)-query(l-1); }
}bit;
 
int LC[MAXV+10], RC[MAXV+10];
 
int ncnt;
 
int newNode()
{
	if(ncnt+1==MAXV) while(1);
	return ++ncnt;
}
 
vector<int> adj[MAXV+10];
vector<int> radj[MAXN+10];
 
void addEdge(int u, int v)
{
	//printf("%d %d\n", u, v);
	if(u==-1 || v==-1) return;
	adj[u].push_back(v);
}
 
void makeTree(int node, int tl, int tr)
{
	if(tr-tl<=2) return;
	int mid=tl+tr>>1;
	LC[node]=newNode();
	RC[node]=newNode();
	addEdge(LC[node], node);
	addEdge(RC[node], node);
	makeTree(LC[node], tl, mid);
	makeTree(RC[node], mid+1, tr);
}
 
int update(int node, int tl, int tr, int p, int k)
{
	if(p<tl || tr<p) return node;
	if(tl==tr)
	{
		if(k>0) return k;
		return -1;
	}
	int ret=newNode();
	int mid=tl+tr>>1;
	LC[ret]=update(LC[node], tl, mid, p, k);
	RC[ret]=update(RC[node], mid+1, tr, p, k);
	addEdge(LC[ret], ret);
	addEdge(RC[ret], ret);
	return ret;
}
 
void query(int node, int tl, int tr, int l, int r, int k)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		addEdge(node, k);
		radj[k].push_back(node);
		return;
	}
	int mid=tl+tr>>1;
	query(LC[node], tl, mid, l, r, k);
	query(RC[node], mid+1, tr, l, r, k);
}
 
bool vis[MAXV+10];
vector<int> S;
void dfs(int now)
{
	vis[now]=true;
	for(int nxt : adj[now])
	{
		if(vis[nxt]) continue;
		dfs(nxt);
	}
	S.push_back(now);
}
 
int scc[MAXV+10], scnt;
void dfs2(int now)
{
	scc[now]=scnt;
	if(now>N+M)
	{
		int nxt=LC[now];
		if(nxt!=-1 && !scc[nxt]) dfs2(nxt);
		nxt=RC[now];
		if(nxt!=-1 && !scc[nxt]) dfs2(nxt);
	}
	else for(int nxt : radj[now])
	{
		if(scc[nxt]) continue;
		dfs2(nxt);
	}
}
 
int main()
{
	int t;
	scanf("%d%d%d", &W, &H, &t);
	for(int i=1; i<=t; i++)
	{
		Line p;
		scanf("%d%d%d%d", &p.x1, &p.y1, &p.x2, &p.y2);
		xcomp.push_back(p.x1);
		xcomp.push_back(p.x2);
		ycomp.push_back(p.y1);
		ycomp.push_back(p.y2);
		if(p.x1==p.x2) B[++M]=p;
		else A[++N]=p;
	}
 
	xcomp.push_back(0);
	ycomp.push_back(0);
	xcomp.push_back(W);
	ycomp.push_back(H);
 
	A[++N]={0, 0, W, 0};
	A[++N]={0, H, W, H};
	B[++M]={0, 0, 0, H};
	B[++M]={W, 0, W, H};
 
	sort(xcomp.begin(), xcomp.end());
	xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
	sort(ycomp.begin(), ycomp.end());
	ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
 
	SX=xcomp.size(); SY=ycomp.size();
 
	for(int i=1; i<=N; i++)
	{
		A[i].x1=lower_bound(xcomp.begin(), xcomp.end(), A[i].x1)-xcomp.begin()+1;
		A[i].x2=lower_bound(xcomp.begin(), xcomp.end(), A[i].x2)-xcomp.begin()+1;
		A[i].y1=lower_bound(ycomp.begin(), ycomp.end(), A[i].y1)-ycomp.begin()+1;
		A[i].y2=lower_bound(ycomp.begin(), ycomp.end(), A[i].y2)-ycomp.begin()+1;
		A[i].p=newNode();
	}
	for(int i=1; i<=M; i++)
	{
		B[i].x1=lower_bound(xcomp.begin(), xcomp.end(), B[i].x1)-xcomp.begin()+1;
		B[i].x2=lower_bound(xcomp.begin(), xcomp.end(), B[i].x2)-xcomp.begin()+1;
		B[i].y1=lower_bound(ycomp.begin(), ycomp.end(), B[i].y1)-ycomp.begin()+1;
		B[i].y2=lower_bound(ycomp.begin(), ycomp.end(), B[i].y2)-ycomp.begin()+1;
		B[i].p=newNode();
	}
	xcomp.clear(); xcomp.shrink_to_fit();
	ycomp.clear(); ycomp.shrink_to_fit();
 
	for(int i=1; i<=N; i++)
	{
		E+=A[i].x2-A[i].x1;
		V+=A[i].x2-A[i].x1+1;
	}
	for(int i=1; i<=M; i++)
	{
		E+=B[i].y2-B[i].y1;
		V+=B[i].y2-B[i].y1+1;
	}
 
	sort(B+1, B+M+1, [&](const Line &p, const Line &q)
	{
		return p.x1<q.x1;
	});
 
	vector<pair<pll, int>> VV;
	for(int i=1; i<=N; i++)
	{
		VV.push_back({{A[i].x1, A[i].y1}, 1});
		VV.push_back({{A[i].x2+1, A[i].y1}, -1});
	}
	sort(VV.begin(), VV.end());
 
	for(int i=1, j=0; i<=M; i++)
	{
		for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
		{
			bit.update(VV[j].first.second, VV[j].second);
		}
		V-=bit.query(B[i].y1, B[i].y2);
	}
 
	int root;
 
	VV.clear(); VV.shrink_to_fit();
	for(int i=1; i<=N; i++)
	{
		VV.push_back({{A[i].x1, A[i].y1}, A[i].p});
		VV.push_back({{A[i].x2+1, A[i].y1}, 0});
	}
	sort(VV.begin(), VV.end());
 
	root=newNode();
	makeTree(root, 1, SY);
	for(int i=1, j=0; i<=M; i++)
	{
		for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
		{
			root=update(root, 1, SY, VV[j].first.second, VV[j].second);
			//printf("!!%d\n", VV[j].second);
		}
		query(root, 1, SY, B[i].y1, B[i].y2, B[i].p);
		//printf("??%d\n", B[i].p);
	}
 
	VV.clear(); VV.shrink_to_fit();
	for(int i=1; i<=M; i++)
	{
		VV.push_back({{B[i].y1, B[i].x1}, B[i].p});
		VV.push_back({{B[i].y2+1, B[i].x1}, 0});
	}
	sort(VV.begin(), VV.end());
	sort(A+1, A+N+1, [&](const Line &p, const Line &q)
	{
		return p.y1<q.y1;
	});

 
	root=newNode();
	makeTree(root, 1, SX);
	for(int i=1, j=0; i<=N; i++)
	{
		for(; j<VV.size() && VV[j].first.first<=A[i].y1; j++)
		{
			root=update(root, 1, SX, VV[j].first.second, VV[j].second);
		}
		query(root, 1, SX, A[i].x1, A[i].x2, A[i].p);
	}
 
	VV.clear(); VV.shrink_to_fit();
	for(int i=1; i<=N+M; i++)
	{
		if(vis[i]) continue;
		dfs(i);
	}
	reverse(S.begin(), S.end());
	for(auto it : S)
	{
		if(scc[it]) continue;
		++scnt;
		dfs2(it);
	}
 
	set<int> SS;
	for(int i=1; i<=N+M; i++) SS.insert(scc[i]);
	C=SS.size();
 
	ll ans=C-V+E;
	printf("%lld\n", ans);
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'void makeTree(int, int, int)':
2014_ho_t5.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int mid=tl+tr>>1;
      |          ~~^~~
2014_ho_t5.cpp: In function 'int update(int, int, int, int, int)':
2014_ho_t5.cpp:76:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |  int mid=tl+tr>>1;
      |          ~~^~~
2014_ho_t5.cpp: In function 'void query(int, int, int, int, int, int)':
2014_ho_t5.cpp:93:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |  int mid=tl+tr>>1;
      |          ~~^~~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:207:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |   for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
      |         ~^~~~~~~~~~
2014_ho_t5.cpp:228:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |   for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
      |         ~^~~~~~~~~~
2014_ho_t5.cpp:254:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |   for(; j<VV.size() && VV[j].first.first<=A[i].y1; j++)
      |         ~^~~~~~~~~~
2014_ho_t5.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |  scanf("%d%d%d", &W, &H, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |   scanf("%d%d%d%d", &p.x1, &p.y1, &p.x2, &p.y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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