oj.uz

Submission #55181

# Submission time Handle Problem Language Result Execution time Memory
55181 2018-07-06T08:53:08 Z khsoo01(#2065) None (JOI14_ho_t5) C++11
30 / 100
 3000 ms 198116 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 100005, L = 262144;

int w, h, n;
int a[N], b[N], c[N], d[N];

long long ans;

bool isx[N], vis[N];

vector<int> xc, yc;

struct segtree {
	set<pii> v[2*L];
	vector<int> w[2*L];
	void upd (int S, int E, int X, int I) {
		S += L;
		E += L;
		while(S<=E) {
			if(S%2 == 1) {
				v[S].insert({X, I});
				w[S].push_back(X);
				S++;
			}
			if(E%2 == 0) {
				v[E].insert({X, I});
				w[E].push_back(X);
				E--;
			}
			S /= 2;
			E /= 2;
		}
	}
	void build () {
		for(int i=0;i<2*L;i++) {
			sort(w[i].begin(), w[i].end());
		}
	}
	int get (int S, int E, int X) {
		X += L;
		while(X) {
			while(true) {
				auto it = v[X].lower_bound({S, 0});
				if(it == v[X].end() || (*it).X > E) break;
				int I = (*it).Y;
				v[X].erase(it);
				if(!vis[I]) return I;
			}
			X /= 2;
		}
		return -1;
	}
	int cnt (int S, int E, int X) {
		X += L;
		int R = 0;
		while(X) {
			R += upper_bound(w[X].begin(), w[X].end(), E) - lower_bound(w[X].begin(), w[X].end(), S);
			X /= 2;
		}
		return R;
	}
} seg[2];

struct sex {
	int s, e, x;
} s[N];

int cpr (vector<int> &V, int X) {
	return lower_bound(V.begin(), V.end(), X) - V.begin();
}

void dfs (int I) {
	vis[I] = true;
	while(true) {
		int T;
		T = seg[isx[I]].get(s[I].s, s[I].e, s[I].x);
		if(T == -1) break;
		dfs(T);
	}
}

int main()
{
	scanf("%d%d%d",&w,&h,&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d%d",&a[i],&c[i],&b[i],&d[i]);
	}
	a[n+1] = 0; b[n+1] = 0; c[n+1] = 0; d[n+1] = h;
	a[n+2] = w; b[n+2] = w; c[n+2] = 0; d[n+2] = h;
	a[n+3] = 0; b[n+3] = w; c[n+3] = 0; d[n+3] = 0;
	a[n+4] = 0; b[n+4] = w; c[n+4] = h; d[n+4] = h;
	n += 4;
	for(int i=1;i<=n;i++) {
		xc.push_back(a[i]);
		xc.push_back(b[i]);
		yc.push_back(c[i]);
		yc.push_back(d[i]);
	}
	sort(xc.begin(), xc.end());
	sort(yc.begin(), yc.end());
	xc.erase(unique(xc.begin(), xc.end()), xc.end());
	yc.erase(unique(yc.begin(), yc.end()), yc.end());
	for(int i=1;i<=n;i++) {
		a[i] = cpr(xc, a[i]);
		b[i] = cpr(xc, b[i]);
		c[i] = cpr(yc, c[i]);
		d[i] = cpr(yc, d[i]);
		int A = a[i], B = b[i], C = c[i], D = d[i];
		if(A == B) {
			isx[i] = true;
			s[i] = {C, D, A};
			seg[0].upd(C, D, A, i);
		}
		else {
			s[i] = {A, B, C};
			seg[1].upd(A, B, C, i);
		}
	}
	seg[0].build();
	seg[1].build();
	for(int i=1;i<=n;i++) {
		ans += seg[isx[i]].cnt(s[i].s, s[i].e, s[i].x);
	}
	ans /= 2;
	ans -= n;
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			dfs(i);
			ans++;
		}
	}
	printf("%lld\n",ans);
}

Compilation message

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:89: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:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&a[i],&c[i],&b[i],&d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 74232 KB Output is correct
2 Correct 69 ms 74344 KB Output is correct
3 Correct 68 ms 74344 KB Output is correct
4 Correct 62 ms 74600 KB Output is correct
5 Correct 62 ms 74600 KB Output is correct
6 Correct 65 ms 74600 KB Output is correct
7 Correct 68 ms 74872 KB Output is correct
8 Correct 67 ms 75132 KB Output is correct
9 Correct 77 ms 75132 KB Output is correct
10 Correct 70 ms 75212 KB Output is correct
11 Correct 70 ms 75244 KB Output is correct
12 Correct 68 ms 75244 KB Output is correct
13 Correct 84 ms 75300 KB Output is correct
14 Correct 75 ms 75300 KB Output is correct
15 Correct 85 ms 75300 KB Output is correct
16 Correct 71 ms 75300 KB Output is correct
17 Correct 79 ms 75300 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 74232 KB Output is correct
2 Correct 69 ms 74344 KB Output is correct
3 Correct 68 ms 74344 KB Output is correct
4 Correct 62 ms 74600 KB Output is correct
5 Correct 62 ms 74600 KB Output is correct
6 Correct 65 ms 74600 KB Output is correct
7 Correct 68 ms 74872 KB Output is correct
8 Correct 67 ms 75132 KB Output is correct
9 Correct 77 ms 75132 KB Output is correct
10 Correct 70 ms 75212 KB Output is correct
11 Correct 70 ms 75244 KB Output is correct
12 Correct 68 ms 75244 KB Output is correct
13 Correct 84 ms 75300 KB Output is correct
14 Correct 75 ms 75300 KB Output is correct
15 Correct 85 ms 75300 KB Output is correct
16 Correct 71 ms 75300 KB Output is correct
17 Correct 79 ms 75300 KB Output is correct
18 Correct 65 ms 75300 KB Output is correct
19 Correct 68 ms 75300 KB Output is correct
20 Correct 72 ms 75300 KB Output is correct
21 Correct 86 ms 75496 KB Output is correct
22 Correct 80 ms 75496 KB Output is correct
23 Correct 76 ms 75496 KB Output is correct
24 Correct 75 ms 75624 KB Output is correct
25 Correct 71 ms 75624 KB Output is correct
26 Correct 77 ms 75624 KB Output is correct
27 Correct 85 ms 75784 KB Output is correct
28 Correct 82 ms 75784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 75784 KB Output is correct
2 Correct 85 ms 75784 KB Output is correct
3 Correct 77 ms 75784 KB Output is correct
4 Correct 84 ms 75824 KB Output is correct
5 Correct 172 ms 82264 KB Output is correct
6 Correct 830 ms 107508 KB Output is correct
7 Correct 1696 ms 140584 KB Output is correct
8 Correct 1634 ms 146172 KB Output is correct
9 Correct 1010 ms 146172 KB Output is correct
10 Correct 379 ms 146172 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 146172 KB Output is correct
2 Correct 79 ms 146172 KB Output is correct
3 Correct 250 ms 146172 KB Output is correct
4 Correct 83 ms 146172 KB Output is correct
5 Correct 72 ms 146172 KB Output is correct
6 Execution timed out 3043 ms 198116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 74232 KB Output is correct
2 Correct 69 ms 74344 KB Output is correct
3 Correct 68 ms 74344 KB Output is correct
4 Correct 62 ms 74600 KB Output is correct
5 Correct 62 ms 74600 KB Output is correct
6 Correct 65 ms 74600 KB Output is correct
7 Correct 68 ms 74872 KB Output is correct
8 Correct 67 ms 75132 KB Output is correct
9 Correct 77 ms 75132 KB Output is correct
10 Correct 70 ms 75212 KB Output is correct
11 Correct 70 ms 75244 KB Output is correct
12 Correct 68 ms 75244 KB Output is correct
13 Correct 84 ms 75300 KB Output is correct
14 Correct 75 ms 75300 KB Output is correct
15 Correct 85 ms 75300 KB Output is correct
16 Correct 71 ms 75300 KB Output is correct
17 Correct 79 ms 75300 KB Output is correct
18 Correct 65 ms 75300 KB Output is correct
19 Correct 68 ms 75300 KB Output is correct
20 Correct 72 ms 75300 KB Output is correct
21 Correct 86 ms 75496 KB Output is correct
22 Correct 80 ms 75496 KB Output is correct
23 Correct 76 ms 75496 KB Output is correct
24 Correct 75 ms 75624 KB Output is correct
25 Correct 71 ms 75624 KB Output is correct
26 Correct 77 ms 75624 KB Output is correct
27 Correct 85 ms 75784 KB Output is correct
28 Correct 82 ms 75784 KB Output is correct
29 Correct 83 ms 75784 KB Output is correct
30 Correct 85 ms 75784 KB Output is correct
31 Correct 77 ms 75784 KB Output is correct
32 Correct 84 ms 75824 KB Output is correct
33 Correct 172 ms 82264 KB Output is correct
34 Correct 830 ms 107508 KB Output is correct
35 Correct 1696 ms 140584 KB Output is correct
36 Correct 1634 ms 146172 KB Output is correct
37 Correct 1010 ms 146172 KB Output is correct
38 Correct 379 ms 146172 KB Output is correct
39 Correct 74 ms 146172 KB Output is correct
40 Correct 79 ms 146172 KB Output is correct
41 Correct 250 ms 146172 KB Output is correct
42 Correct 83 ms 146172 KB Output is correct
43 Correct 72 ms 146172 KB Output is correct
44 Execution timed out 3043 ms 198116 KB Time limit exceeded
45 Halted 0 ms 0 KB -