QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#573388#3160. Cuttingcrimson23120 236ms98032kbC++234.6kb2024-09-18 18:31:342024-09-18 18:31:34

Judging History

This is the latest submission verdict.

  • [2024-09-18 18:31:34]
  • Judged
  • Verdict: 20
  • Time: 236ms
  • Memory: 98032kb
  • [2024-09-18 18:31:34]
  • Submitted

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
typedef long long ll;
typedef std::vector<int> Vint;
typedef std::vector<ll> Vll;
typedef std::set<int> Sint;
typedef std::unordered_set<int> USint;
const int LEN = 1e5 + 10;

#define ADD 1
#define DEL -1

//#define MAP

int N, w, h, xi, yi;
int P[LEN];//disjoint set
int find(int i) { return P[i] < 0 ? i : P[i] = find(P[i]); }
bool join(int i, int j) {
	i = find(i), j = find(j);
	if (i == j) return 0;
	if (P[i] < P[j]) P[i] += P[j], P[j] = i;
	else P[j] += P[i], P[i] = j;
	return 1;
}
int idx_bi_search(const Vint& A, const int& x) {
	int s = 0, e = A.size() - 1, m;
	while (s <= e) {
		m = s + e >> 1;
		if (A[m] == x) return m;
		else if (A[m] > x) e = m - 1;
		else s = m + 1;
	}
	return -1;
}
struct H_event {
	int l, r, y, i;
	H_event(int l_ = 0, int r_ = 0, int y_ = 0, int i_ = 0) : l(l_), r(r_), y(y_), i(i_) {}
	bool operator < (const H_event& h) const { return y == h.y ? l < h.l : y < h.y; }
} H[LEN]; int hp;
struct V_event {
	int x, y, ev, i;
	V_event(int x_ = 0, int y_ = 0, int ev_ = 0, int i_ = 0) : x(x_), y(y_), ev(ev_), i(i_) {}
	bool operator < (const V_event& v) const { return y == v.y ? x < v.x : y < v.y; }
} V[LEN << 1]; int vp;
int hi_y[LEN];//highest y coord' of vertical event
//USint inxs[LEN << 4];//seg_tree
Sint inxs[LEN << 4];//seg_tree
int seg_v[LEN << 4];//seg_tree
int seg_p[LEN << 4];//seg_tree
void update_vertical(const int& x, const int& ev, const int& idx, int s = 0, int e = xi - 1, int i = 1) {
	if (x < s || e < x) return;
	if (ev == ADD) inxs[i].insert(idx);
	else if (ev == DEL) {
		inxs[i].erase(idx);
		if (seg_v[i] == idx) seg_v[i] = -1;//erase all vertical
	}
	if (s == e) { seg_p[i] += ev; return; }
	int m = s + e >> 1;
	update_vertical(x, ev, idx, s, m, i << 1);
	update_vertical(x, ev, idx, m + 1, e, i << 1 | 1);
	seg_p[i] = seg_p[i << 1] + seg_p[i << 1 | 1];
	return;
}
int sum_horizontal(const int& l, const int& r, const int& idx, int s = 0, int e = xi - 1, int i = 1) {
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) {
		if (seg_v[i] != -1) join(idx, seg_v[i]);//find new intersection
		for (const int& v : inxs[i]) {
			join(idx, v);
			if (seg_v[i] == -1 || hi_y[v] > hi_y[seg_v[i]]) seg_v[i] = v;//highest y coord'
		}
		inxs[i].clear();
		return seg_p[i];
	}
	int m = s + e >> 1;
	return sum_horizontal(l, r, idx, s, m, i << 1) + sum_horizontal(l, r, idx, m + 1, e, i << 1 | 1);
}
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cin >> h >> w >> N;
	Vint X = { 0, w };
	Vint Y = { 0, h, h + 1 };
	hp = 0; vp = 0;
	for (int i = 0, a, b, c, d; i < N; i++) {
		std::cin >> a >> b >> c >> d;
		if (a != c) {
			H[hp++] = H_event(a, c, b, i);
		}
		else if (b != d) {
			hi_y[i] = d;
			d++;
			V[vp++] = V_event(a, b, ADD, i);
			V[vp++] = V_event(a, d, DEL, i);
		}
		X.push_back(a); X.push_back(c);
		Y.push_back(b); Y.push_back(d);
	}
	H[hp++] = H_event(0, w, 0, N);
	H[hp++] = H_event(0, w, h, N);
	V[vp++] = V_event(0, 0, ADD, N);
	V[vp++] = V_event(w, 0, ADD, N);
	V[vp++] = V_event(0, h + 1, DEL, N);
	V[vp++] = V_event(w, h + 1, DEL, N);

	std::sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
	std::sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());
	std::sort(H, H + hp);
	std::sort(V, V + vp);
	memset(P, -1, sizeof P);
	memset(seg_v, -1, sizeof seg_v);
	memset(seg_p, 0, sizeof seg_p);

	xi = X.size();
	yi = Y.size();

#ifdef MAP
	std::unordered_map<int, int> mx;
	for (int i = 0; i < xi; i++) mx[X[i]] = i;
#endif

	ll e = 0, v = 0, chi = 0;
	for (int y = 0, i = 0, j = 0; y < yi; y++) {
		//while (i < vp && idx_bi_search(Y, V[i].y) == y) {//vertical events
		while (i < vp && V[i].y == Y[y]) {//vertical events
			v++;
			e += V[i].ev == DEL;
			update_vertical(idx_bi_search(X, V[i].x), V[i].ev, V[i].i);
			i++;
		}
		//while (j < hp && idx_bi_search(Y, H[j].y) == y) {//horizontal events
		while (j < hp && H[j].y == Y[y]) {//horizontal events
#ifdef MAP
			int l_ = mx[H[j].l];
			int r_ = mx[H[j].r];
#else
			int l_ = idx_bi_search(X, H[j].l);
			int r_ = idx_bi_search(X, H[j].r);
#endif
			int cnt = sum_horizontal(l_, r_, H[j].i);
			e += cnt * 2 + 1;
			v += cnt + 2;
			j++;
		}
	}
	for (int i = 0; i <= N; i++) if (i == find(i)) chi++;
	std::cout << chi - v + e << "\n";//X = v - e + f
	return;
}
int main() { solve(); return 0; }//boj10049 cutting  refer to Jay0202

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 4ms
memory: 96564kb

input:

10 10 10
6 5 6 10
4 0 4 3
3 2 3 10
0 8 2 8
3 8 5 8
0 2 7 2
9 6 9 8
8 2 8 7
5 3 6 3
1 1 7 1

output:

3

result:

ok single line: '3'

Test #2:

score: 5
Accepted
time: 14ms
memory: 96572kb

input:

10 10 10
5 7 8 7
3 3 4 3
0 5 10 5
9 0 9 8
5 2 9 2
2 1 2 7
0 8 8 8
7 0 7 1
2 7 4 7
9 9 10 9

output:

3

result:

ok single line: '3'

Test #3:

score: 5
Accepted
time: 3ms
memory: 96568kb

input:

10 10 15
1 1 4 1
5 8 9 8
4 2 4 3
5 1 5 7
5 1 10 1
9 8 9 10
3 3 3 8
1 0 1 9
9 0 9 5
9 9 10 9
1 9 7 9
2 5 3 5
4 4 4 6
5 4 8 4
1 7 9 7

output:

4

result:

ok single line: '4'

Test #4:

score: 5
Accepted
time: 12ms
memory: 96700kb

input:

100 100 100
31 29 31 83
36 54 36 77
11 16 51 16
20 24 20 82
7 1 7 43
46 14 64 14
77 35 77 94
8 26 82 26
59 43 85 43
55 18 94 18
97 22 97 90
46 61 75 61
78 6 78 20
74 3 74 85
34 93 97 93
87 45 98 45
57 23 82 23
5 58 64 58
55 92 58 92
9 10 9 49
8 5 57 5
17 88 61 88
48 68 48 73
53 51 93 51
7 29 85 29
5...

output:

303

result:

ok single line: '303'

Test #5:

score: 5
Accepted
time: 3ms
memory: 96636kb

input:

100 100 144
47 22 89 22
12 12 12 99
94 21 94 64
83 93 83 98
27 29 78 29
18 43 76 43
19 57 29 57
22 33 22 90
71 61 82 61
27 1 27 100
9 47 56 47
37 34 44 34
32 23 89 23
35 58 89 58
8 78 13 78
97 90 97 91
19 7 39 7
29 27 55 27
80 79 88 79
33 8 76 8
6 48 54 48
46 73 46 97
48 53 61 53
92 52 92 53
10 19 2...

output:

781

result:

ok single line: '781'

Test #6:

score: 5
Accepted
time: 8ms
memory: 96644kb

input:

1000 1000 100
17 471 249 471
196 109 196 958
49 508 319 508
374 994 495 994
816 583 816 903
543 168 975 168
641 405 641 985
675 13 995 13
5 7 795 7
927 44 927 503
997 163 997 205
874 293 907 293
159 131 159 466
214 796 958 796
275 938 908 938
390 30 390 978
527 29 527 511
426 61 799 61
458 820 849 8...

output:

157

result:

ok single line: '157'

Test #7:

score: 5
Accepted
time: 4ms
memory: 96692kb

input:

1000 1000 500
49 222 462 222
177 9 177 400
101 731 622 731
901 278 901 706
383 577 383 776
743 409 743 660
326 552 770 552
819 543 819 931
303 383 324 383
43 153 43 298
597 788 602 788
583 991 771 991
25 35 25 944
839 571 839 660
7 82 7 647
585 379 585 973
77 261 983 261
4 7 351 7
240 214 240 690
69...

output:

6684

result:

ok single line: '6684'

Test #8:

score: 5
Accepted
time: 11ms
memory: 96728kb

input:

1000 1000 1000
885 146 885 416
41 230 41 930
620 29 620 969
634 947 720 947
569 153 575 153
894 252 894 374
215 463 215 960
437 758 669 758
46 968 664 968
86 217 86 737
110 660 850 660
548 574 548 917
229 399 229 864
365 533 706 533
85 509 565 509
206 523 371 523
203 273 848 273
566 415 566 694
391 ...

output:

31514

result:

ok single line: '31514'

Test #9:

score: 5
Accepted
time: 13ms
memory: 96648kb

input:

1000 1000 1000
525 571 525 588
617 830 617 871
399 482 399 505
973 863 978 863
233 274 233 292
899 21 899 69
175 367 219 367
701 938 701 969
681 622 716 622
484 968 492 968
812 108 834 108
708 258 749 258
657 871 678 871
750 452 750 466
606 384 613 384
759 146 759 188
2 949 13 949
140 502 164 502
80...

output:

2

result:

ok single line: '2'

Test #10:

score: 5
Accepted
time: 8ms
memory: 96712kb

input:

1000 1000 1000
966 623 966 966
793 681 793 939
653 827 886 827
216 201 216 478
538 170 755 170
311 800 311 1000
698 211 999 211
93 60 93 300
262 971 573 971
368 461 598 461
442 674 812 674
558 476 803 476
696 997 951 997
771 724 998 724
205 869 510 869
3 124 758 124
235 18 485 18
373 523 373 974
149...

output:

23422

result:

ok single line: '23422'

Test #11:

score: 5
Accepted
time: 7ms
memory: 96988kb

input:

1000 1000 1000
505 365 505 966
230 81 230 775
463 97 463 787
293 808 941 808
72 884 990 884
989 20 989 857
532 182 532 940
428 119 428 857
374 317 993 317
38 908 998 908
273 37 273 942
648 43 648 997
451 349 451 983
174 233 989 233
188 148 962 148
297 13 297 969
100 379 841 379
383 428 993 428
44 61...

output:

136910

result:

ok single line: '136910'

Test #12:

score: 5
Accepted
time: 11ms
memory: 96636kb

input:

1000 1000 500
585 56 585 801
152 785 470 785
273 498 851 498
484 304 703 304
79 731 984 731
774 825 774 865
475 110 727 110
387 768 387 901
564 265 564 866
248 729 974 729
713 55 713 490
632 869 1000 869
235 585 918 585
601 272 928 272
747 177 747 895
695 192 695 966
517 15 517 357
132 571 602 571
8...

output:

20555

result:

ok single line: '20555'

Test #13:

score: 5
Accepted
time: 17ms
memory: 96764kb

input:

1000 1000 1000
377 476 377 567
1 130 1 939
164 183 164 575
801 10 801 178
180 184 180 940
446 16 446 840
398 855 820 855
51 180 51 982
632 105 632 822
78 91 537 91
378 181 378 946
21 655 400 655
275 4 275 955
579 314 579 491
108 589 944 589
841 437 841 911
794 258 794 851
224 31 224 927
473 147 473 ...

output:

100268

result:

ok single line: '100268'

Test #14:

score: 0
Wrong Answer
time: 15ms
memory: 96760kb

input:

1000 100 1000
795 13 795 92
0 13 968 13
243 14 243 82
19 54 1000 54
192 2 192 5
270 38 270 73
133 2 133 3
992 57 992 63
20 4 20 14
381 0 381 35
904 45 904 89
51 1 951 1
480 34 480 62
281 50 281 90
371 26 371 45
113 62 113 65
598 28 598 63
158 84 965 84
537 1 537 96
897 61 897 98
768 12 768 89
762 37...

output:

34541

result:

wrong answer 1st lines differ - expected: '34510', found: '34541'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 20
Accepted

Test #29:

score: 20
Accepted
time: 4ms
memory: 96644kb

input:

1000 1000 600
467 160 467 845
10 68 10 101
358 513 358 621
66 671 620 671
351 549 596 549
87 746 87 917
526 145 526 559
118 314 118 868
87 584 373 584
4 117 4 150
801 265 801 416
417 269 417 630
480 144 480 550
945 203 945 768
679 484 679 525
93 342 93 504
954 176 954 270
453 206 453 565
898 668 898...

output:

10525

result:

ok single line: '10525'

Test #30:

score: 20
Accepted
time: 14ms
memory: 96932kb

input:

1000 1000000000 603
601 755190731 601 810458592
934 408413681 934 991509232
677 999530155 815 999530155
168 493643722 673 493643722
471 611014716 471 737416010
297 338288031 560 338288031
359 95457712 359 618830356
526 343959777 881 343959777
925 444786130 925 668860824
514 666804490 514 983701500
6...

output:

9023

result:

ok single line: '9023'

Test #31:

score: 20
Accepted
time: 12ms
memory: 96696kb

input:

1000000000 1000 497
827959903 211 827959903 713
423671814 326 423671814 505
151915634 787 151915634 939
973586233 330 973586233 372
243989833 294 381424364 294
852825911 110 852825911 211
656054851 649 980370982 649
361463145 400 562481084 400
598057245 206 598057245 519
356401865 441 356401865 641
...

output:

6182

result:

ok single line: '6182'

Test #32:

score: 20
Accepted
time: 11ms
memory: 96704kb

input:

1000000000 1000000000 1000
630608407 74813188 630608407 572572115
428810287 713956480 539731989 713956480
640066404 189916304 777953387 189916304
139692089 138020424 436628489 138020424
232274854 245431711 232274854 706217149
76021996 254360470 90280084 254360470
78051453 144768536 78051453 46597063...

output:

7634

result:

ok single line: '7634'

Test #33:

score: 20
Accepted
time: 31ms
memory: 96904kb

input:

1000000000 1000000000 10000
669049628 139158927 669049628 226133259
718482206 453214864 721640027 453214864
922685361 202362178 922685361 269486043
176418025 189329098 176418025 207938401
924551310 799389698 971274232 799389698
913658655 45406740 913658655 115315119
684126650 488289248 684126650 538...

output:

49135

result:

ok single line: '49135'

Test #34:

score: 20
Accepted
time: 113ms
memory: 97100kb

input:

1000000000 1000000000 50000
238613172 391515513 238613172 405815949
228020608 514039210 228020608 525135195
764909506 76206052 767077509 76206052
120043781 289917261 130315212 289917261
838856354 367766371 838856354 377711111
190255664 959215979 190255664 960991962
152573495 152153917 162261418 1521...

output:

23820

result:

ok single line: '23820'

Test #35:

score: 20
Accepted
time: 236ms
memory: 98032kb

input:

1000000000 1000000000 100000
170340118 373306152 170340118 379627430
12604058 168765839 12604058 170795182
20332951 541320438 20332951 549298071
134940794 461595827 134940794 470870367
311164461 197351124 311164461 202291947
421842363 147731250 422869432 147731250
282491926 152715320 282491926 15528...

output:

9721

result:

ok single line: '9721'

Test #36:

score: 20
Accepted
time: 222ms
memory: 97980kb

input:

1000000000 1000000000 100000
648681835 61387068 648681835 61467529
482483617 633133302 490538368 633133302
238416060 954280004 238416060 960579571
971671652 48097001 971671652 52691091
961774046 226207867 961774046 234611274
143188037 361192114 152157365 361192114
631586268 619581854 639748156 61958...

output:

23400

result:

ok single line: '23400'

Test #37:

score: 20
Accepted
time: 179ms
memory: 97720kb

input:

1000000000 1000000000 100000
533066721 267929372 533066721 268068695
478609871 93625392 478609871 94238869
509029333 579208129 509709352 579208129
712522492 727418412 712719154 727418412
272180063 572902914 272180063 573774712
758504262 227729418 759289998 227729418
637434739 129362617 637434739 130...

output:

1

result:

ok single line: '1'

Test #38:

score: 20
Accepted
time: 151ms
memory: 97908kb

input:

1000000000 1000000000 100000
273576603 753501145 273576631 753501145
209049647 751024536 209049647 751024584
730324450 156458455 730324489 156458455
462842489 975962094 462842489 975962116
539789616 391587975 539789616 391588008
443086141 242291883 443086228 242291883
935928542 938420909 935928542 9...

output:

1

result:

ok single line: '1'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%