QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#573388 | #3160. Cutting | crimson231 | 20 | 236ms | 98032kb | C++23 | 4.6kb | 2024-09-18 18:31:34 | 2024-09-18 18:31:34 |
Judging History
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%