oj.uz

Submission #55202

# Submission time Handle Problem Language Result Execution time Memory
55202 2018-07-06T10:12:30 Z 김세빈(#1527) None (JOI14_ho_t5) C++11
20 / 100
 427 ms 48492 KB 
#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;
ll A[202020], B[202020], C[202020], D[202020];
ll T[606060];
ll n, v, e, w, h, sz;

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());
	
	printf("%lld\n", e - v + 1);
	
	return 0;
}

Compilation message

2014_ho_t5.cpp: In function 'll get_sum(ll, ll)':
2014_ho_t5.cpp:29:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l+1 >> 1;
       ~^~
2014_ho_t5.cpp:30:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r-1 >> 1;
       ~^~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:74: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:74: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:53: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:59: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 24184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 24184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 24296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24296 KB Output is correct
2 Correct 26 ms 24380 KB Output is correct
3 Correct 63 ms 26516 KB Output is correct
4 Correct 28 ms 26516 KB Output is correct
5 Correct 27 ms 26516 KB Output is correct
6 Correct 427 ms 48492 KB Output is correct
7 Correct 35 ms 48492 KB Output is correct
8 Correct 254 ms 48492 KB Output is correct
9 Correct 222 ms 48492 KB Output is correct
10 Correct 275 ms 48492 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 24184 KB Output isn't correct
2 Halted 0 ms 0 KB -