Submission #55211

#	Time	Username	Problem	Language	Result	Execution time	Memory
55211		sebinkim	절취선 (JOI14_ho_t5)	C++14	40 / 100	642 ms	62544 KiB

2014_ho_t5

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

vector <ll> X, Y;
vector <pll> LX[202020], LY[202020];
vector <pll> PX[202020], PY[202020], Z[202020];
vector <pll> K;
vector <ll> L[202020], P[202020];
set <pll> S;
ll A[202020], B[202020], C[202020], D[202020];
ll T[606060], U[202020];
ll n, v, e, w, h, sz;

ll find(ll p) { return p == U[p]? p : U[p] = find(U[p]); }
void group(ll a, ll b)
{
	U[find(a)] = find(b);
}

void insert(ll p, ll v)
{
	p += sz;
	for(;p;p>>=1) T[p] += v;
}

ll get_sum(ll l, ll r)
{
	ll ret = 0;
	l += sz, r += sz;
	for(;l<r;){
		if(l & 1) ret += T[l];
		if(~r & 1) ret += T[r];
		l = l+1 >> 1;
		r = r-1 >> 1;
	}
	if(l == r) ret += T[l];
	
	return ret;
}

ll intersects(vector <pll> *E, vector <pll> *V, ll x)
{
	ll i, ret = 0;
	
	for(i=0;i<=x;i++){
		for(auto j: V[i]) insert(j.first, j.second);
		for(auto j: E[i]) ret += get_sum(j.first + 1, j.second - 1);
	}
	
	return ret;
}

int main()
{
	ll i, a, b, c, d;
	
	scanf("%lld%lld%lld", &w, &h, &n);
	
	X.push_back(0); Y.push_back(0);
	X.push_back(w); Y.push_back(h);
	
	for(i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld", A+i, B+i, C+i, D+i);
		X.push_back(A[i]); Y.push_back(B[i]);
		X.push_back(C[i]); Y.push_back(D[i]);
	}
	
	n ++; A[n] = 0, B[n] = 0, C[n] = w, D[n] = 0; 
	n ++; A[n] = 0, B[n] = h, C[n] = w, D[n] = h;
	n ++; A[n] = 0, B[n] = 0, C[n] = 0, D[n] = h;
	n ++; A[n] = w, B[n] = 0, C[n] = w, D[n] = h;
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	sort(Y.begin(), Y.end());
	Y.erase(unique(Y.begin(), Y.end()), Y.end());
	
	for(sz=1;sz<X.size() && sz<Y.size();sz<<=1);
	
	for(i=1;i<=n;i++){
		a = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
		b = lower_bound(Y.begin(), Y.end(), B[i]) - Y.begin();
		c = lower_bound(X.begin(), X.end(), C[i]) - X.begin();
		d = lower_bound(Y.begin(), Y.end(), D[i]) - Y.begin();
		
		if(a == c){
			LX[a].push_back(pll(b, d));
			PY[b].push_back(pll(a, 1));	
			PY[d+1].push_back(pll(a, -1));
			
			if(b+1 <= d){
				Z[b+1].push_back(pll(a, 1));
				Z[d].push_back(pll(a, -1));
			}
		}
		else{
			LY[b].push_back(pll(a, c));
			PX[a].push_back(pll(b, 1));
			PX[c+1].push_back(pll(b, -1));
		}
		
		K.push_back(pll(a, b));
		K.push_back(pll(c, d));
	}
	
	sort(K.begin(), K.end());
	K.erase(unique(K.begin(), K.end()), K.end());
	
	v = K.size() + intersects(LY, Z, (ll)Y.size());
	e = n + intersects(LX, PX, (ll)X.size()) + intersects(LY, PY, (ll)Y.size());
	
	if(e > 5000000){
		printf("%lld\n", e - v + 1);
		return 0;
	}
	
	for(i=1;i<=n;i++){
		A[i] = a = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
		B[i] = b = lower_bound(Y.begin(), Y.end(), B[i]) - Y.begin();
		C[i] = c = lower_bound(X.begin(), X.end(), C[i]) - X.begin();
		D[i] = d = lower_bound(Y.begin(), Y.end(), D[i]) - Y.begin();
		
		U[i] = i;
		
		if(a == c) L[a].push_back(i);
		else{
			P[a].push_back(i);
			P[c+1].push_back(-i);
		}
	}
	
	for(i=0;i<=X.size();i++){
		for(auto j: P[i]){
			if(j < 0) S.erase(pll(B[-j], -j));
			else S.insert(pll(B[j], j));
		}
		for(auto j: L[i]){
			auto it1 = S.lower_bound(pll(B[j], 0));
			auto it2 = S.lower_bound(pll(D[j], 1e9));
			for(; it1 != it2; it1++){
				group(j, it1 -> second);
			}
		}
	}
	
	c = 0;
	for(i=1;i<=n;i++) c += (i == U[i]);
	
	printf("%lld\n", e - v + c );
	
	return 0;
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'll get_sum(ll, ll)':
2014_ho_t5.cpp:37:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l+1 >> 1;
       ~^~
2014_ho_t5.cpp:38:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r-1 >> 1;
       ~^~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:82:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(sz=1;sz<X.size() && sz<Y.size();sz<<=1);
           ~~^~~~~~~~~
2014_ho_t5.cpp:82:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(sz=1;sz<X.size() && sz<Y.size();sz<<=1);
                          ~~^~~~~~~~~
2014_ho_t5.cpp:136:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<=X.size();i++){
          ~^~~~~~~~~~
2014_ho_t5.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &w, &h, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", A+i, B+i, C+i, D+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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