QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114852 | #6639. Disk Tree | jeffqi | AC ✓ | 402ms | 55200kb | C++23 | 1.7kb | 2023-06-23 18:48:43 | 2023-06-23 18:48:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
using namespace std;
namespace qiqi {
struct Data {
int l,r,k;
Data(int l = 0,int r = -1,int k = -1):l(max(l,0)),r(r),k(k) {}
bool friend operator < (Data a,Data b) {
return a.k < b.k;
}
};
void main() {
int n; cin >> n;
vector<Data> a(n);
for (int i = 0; i < n; i++) {
int x,y,r;
cin >> x >> y >> r;
a[i] = Data(x-r,x+r,y);
}
sort(all(a));
map<int,Data> c;
c[-1] = Data();
map<int,int> mx;
vector<array<int,4>> ans;
for (auto [l,r,k]:a) {
auto bit = prev(c.lower_bound(l)),eit = c.upper_bound(r);
Data col = prev(eit)->se;
for (auto it = bit; it != eit; it++) {
int y = it->se.k;
if (y != -1 && (it == bit || prev(it)->se.r < it->se.l)) {
int x = max(l,it->fi);
ans.pb({x,k,x,max(mx[x],y)});
}
}
c.erase(next(bit),eit);
c[l] = Data(l,r,k);
c.emplace(r,col);
mx[l] = mx[r] = k;
}
Data lst;
c.erase(c.begin());
for (auto it = c.begin(); it != c.end(); it++) {
if (it->se.k != -1) {
if (it != c.begin() && prev(it)->se.r < it->se.l) {
ans.pb({it->fi,it->se.k,lst.r,lst.k});
}
lst = it->se;
}
}
cout << "YES\n";
for (auto [a,b,c,d]:ans) {
cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
qiqi::main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3440kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 5 0 0 4 10 4 0
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
2 1 1 1 3 3 1
output:
YES 2 3 2 1
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 10 1 0 19 10 19 0 19 20 19 10 2 20 2 10
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
10 29 29 2 28 55 10 99 81 4 17 82 10 45 88 10 48 68 10 0 8 10 98 95 10 34 0 10 17 24 10
output:
YES 7 24 7 8 24 24 24 0 27 29 27 24 18 55 18 24 38 68 38 55 7 82 7 24 35 88 35 55 95 95 95 81 88 95 58 68
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
100 490 783 12 666 460 55 561 245 6 223 323 25 3 520 77 225 161 24 514 190 16 997 914 100 412 265 100 374 610 36 296 854 39 601 901 2 307 21 100 390 422 24 940 414 32 332 438 35 553 992 100 235 775 3 656 901 37 770 417 22 649 305 100 448 84 3 375 939 77 910 847 9 776 357 37 743 97 100 371 502 39 508...
output:
YES 406 40 406 21 881 52 881 11 891 76 891 11 445 84 445 40 807 97 807 14 842 97 842 52 207 100 207 21 100 115 100 13 432 132 432 40 506 132 506 58 927 132 927 11 968 153 968 132 129 156 129 115 201 161 201 100 420 163 420 40 0 179 0 13 806 183 806 97 498 190 498 132 254 204 254 21 896 204 896 76 81...
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
200 2948 9798 687 3897 647 35 3918 587 28 1262 2717 206 1315 9524 20 2381 305 1000 4344 6858 20 6234 8949 53 5168 4772 85 5044 6109 158 72 7670 132 7300 1213 837 5427 2263 1000 1785 3009 276 6136 1421 43 1629 5620 29 6445 9489 242 8443 3141 1000 4118 4307 63 1874 5238 291 1964 5785 73 7794 3934 18 3...
output:
YES 6889 119 6889 82 7188 187 7188 82 1381 305 1381 51 4121 321 4121 120 7525 350 7525 110 3341 602 3341 305 3890 647 3890 587 3364 769 3364 602 3501 778 3501 602 3547 790 3547 778 3862 790 3862 647 3914 820 3914 790 4212 842 4212 321 5335 842 5335 119 5330 953 5330 842 5971 1005 5971 119 9525 1058 ...
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
300 42942 37079 222 49441 21821 1695 61023 31153 561 86630 26307 352 36940 78253 213 7841 81086 626 47425 22290 374 17694 68695 648 38259 64794 998 43599 46942 9662 9204 2816 1965 38652 83568 4057 4046 29001 1034 72591 63214 587 75984 64859 1112 70005 72177 576 34522 52126 652 56627 48785 1747 78820...
output:
YES 84218 898 84218 679 23920 1356 23920 857 52886 1692 52886 148 66826 1902 66826 148 70301 1902 70301 898 10940 2816 10940 857 68731 4851 68731 1902 30286 5253 30286 728 84121 6075 84121 898 97943 6075 97943 1648 7239 6153 7239 2816 51510 6439 51510 1692 54634 6574 54634 148 74232 7203 74232 898 2...
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
1000 558504245 246224785 100000000 971981730 913036757 1821458 198791767 482624549 5998171 540520619 353988177 8924682 183178222 46223569 9859905 118485076 22129062 7497235 274928891 417171180 372954 230079763 468235825 289869 859092765 562864738 5551376 129036518 743777318 3969979 265158223 3092933...
output:
YES 190661765 3162583 190661765 247311 541864786 6507586 541864786 6502176 743125078 7349609 743125078 4245988 528880268 8856051 528880268 6507586 83764511 11673756 83764511 11198817 533423313 15169165 533423313 6507586 773562974 15193877 773562974 7670508 500313349 15530399 500313349 8856051 383407...
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 2ms
memory: 3944kb
input:
3000 442876143 334276354 3627270 526253918 947313397 2498956 566692880 229330019 4243066 497859604 658736917 13012787 315969653 65582717 1400013 394215653 932651144 1655676 58249045 973232518 860150 860773683 959388251 1594726 23803673 921365885 5926749 730359196 818999592 1521282 971839312 22835235...
output:
YES 637956442 2810902 637956442 2434108 905232001 4333444 905232001 767255 271669766 5948749 271669766 3214844 903657192 6368011 903657192 767255 9297500 7470415 9297500 4543545 639882785 8791833 639882785 2434108 931683190 9127459 931683190 6089018 912528342 9258659 912528342 4333444 689192278 9636...
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 6ms
memory: 4288kb
input:
7000 601805179 978984160 464352 918208048 607538668 2214109 328147216 806677103 3901695 961794394 719893281 1114470 453816635 992288784 274949 778724702 692479905 1170018 169287513 886715521 576156 812072299 118324465 93778 726229729 150105801 3593039 368683874 642143790 1277375 40087476 151799345 4...
output:
YES 476602214 830671 476602214 824708 747341339 1362928 747341339 561575 995526093 2229158 995526093 421260 747340297 2516612 747340297 561575 474778201 2774214 474778201 830671 691292001 4967464 691292001 2984537 706480924 4967464 706480924 2264350 738918550 5153265 738918550 4552317 739080324 5153...
result:
ok answer = 1
Test #11:
score: 0
Accepted
time: 11ms
memory: 4020kb
input:
10000 645 4710 5 1554 4072 7 6505 2760 1 6125 8212 11 9802 9537 3 6584 4356 6 1104 6649 23 4580 2623 20 3107 2460 1 4689 1662 2 7815 161 14 8718 3658 28 2900 63 15 1741 7296 44 8380 4608 50 2212 8514 4 7919 3069 17 1638 6057 3 504 9867 18 7869 8021 14 866 9239 5 3452 8042 4 9049 7222 4 4447 1004 5 9...
output:
YES 7372 3 7372 2 1817 16 1817 9 2165 16 2165 6 7004 17 7004 4 3205 19 3205 8 6926 19 6926 6 8082 20 8082 0 8119 20 8119 12 1801 21 1801 9 8017 22 8017 12 7858 23 7858 11 1811 23 1811 9 25 24 25 8 8917 24 8917 10 3332 25 3332 7 3209 28 3209 8 3213 28 3213 10 7673 29 7673 10 7690 29 7690 1 7710 29 77...
result:
ok answer = 1
Test #12:
score: 0
Accepted
time: 178ms
memory: 15832kb
input:
100000 956095525 596102106 2 461544095 587257542 118 884402350 357055086 14228 547768407 186052059 263162 827807425 303694996 474924 692537425 44608243 131609 504660936 451030143 15134 207539367 899608364 20283 919236289 724317925 6 386476373 727023405 323 781914406 792770865 1064 411548762 2476126 ...
output:
YES 166645748 1282666 166645748 1070655 781495978 1532843 781495978 916946 913092760 2067814 913092760 415667 32717367 2121278 32717367 21634 793859997 2399033 793859997 73849 990073935 2591609 990073935 242572 262745995 2725430 262745995 646735 164387037 2736235 164387037 115731 166570072 2736235 1...
result:
ok answer = 1
Test #13:
score: 0
Accepted
time: 382ms
memory: 28004kb
input:
200000 267774456 105702394 770 297991198 776424841 124 703700092 120262616 341808 212663821 221756923 367 195031049 705083745 66 692227605 63745620 1221 615879799 481139131 3053 93198187 239262367 141042 645539116 89213985 1679 312339485 547897747 2701 546940040 418847605 2 100457345 231142218 2 290...
output:
YES 533322155 783213 533322155 394352 66013409 874685 66013409 846304 352354652 1229643 352354652 1020584 40242506 1281516 40242506 422022 198344953 1325085 198344953 397205 450861574 1526288 450861574 735586 977519343 1600060 977519343 1526572 376708081 1745254 376708081 625535 388077846 1747805 38...
result:
ok answer = 1
Test #14:
score: 0
Accepted
time: 372ms
memory: 28716kb
input:
200000 890760596 387635202 407021 845949678 865384827 250 298937825 444813049 30 257079208 603496538 24935 825947861 514433442 276 664047255 283065064 651111 481691537 759981944 616 953630211 233077236 207 716089940 174481709 876827 807394429 737990862 50258 9195111 176890156 946 209723712 839382384...
output:
YES 37720798 890622 37720798 15881 771018531 1037143 771018531 23372 110302113 1437234 110302113 563840 931048158 1448740 931048158 148518 33789483 1470543 33789483 902588 9388337 1475010 9388337 344915 731784297 1575829 731784297 485975 480865523 1600460 480865523 960314 677102085 1628733 677102085...
result:
ok answer = 1
Test #15:
score: 0
Accepted
time: 395ms
memory: 28076kb
input:
200000 21940906 14228149 878 947616612 637746482 278 490310177 117451293 1714712 278642428 651582650 1 214397046 727562852 3 314365021 93147008 158746 367463298 30253119 650745 816993648 678947261 4384 503557517 182822048 1116 61881753 989787068 109052 632366340 971129473 26 870552310 805607887 5436...
output:
YES 724669680 768403 724669680 187719 710364223 864272 710364223 231495 637091113 955781 637091113 44027 410048543 1242272 410048543 856349 833691349 1270633 833691349 205878 698121189 1394136 698121189 170170 553972465 1460523 553972465 74553 818006780 1474701 818006780 233689 117332845 1509142 117...
result:
ok answer = 1
Test #16:
score: 0
Accepted
time: 267ms
memory: 14428kb
input:
200000 81117 91365 1 68731 21152 3 37456 24002 2 37581 56006 3 52472 65837 1 68592 30967 2 37017 58189 11 21553 64504 95 94147 72332 80 82905 892 21 37593 40659 5 83451 10026 2 24925 11872 13 84418 48948 156 52378 43742 51 27379 10720 162 37042 54394 1 92324 20573 1 69506 96945 133 87826 40634 3 962...
output:
YES 63940 72 63940 32 99012 77 99012 18 34685 80 34685 48 54109 105 54109 7 31278 109 31278 1 50726 110 50726 2 45862 112 45862 48 88980 113 88980 18 13889 114 13889 64 44300 115 44300 4 25581 117 25581 44 23484 120 23484 35 38816 123 38816 32 7913 124 7913 53 20741 125 20741 3 87073 125 87073 69 77...
result:
ok answer = 1
Test #17:
score: 0
Accepted
time: 11ms
memory: 4584kb
input:
10000 126758371 588314899 812231 238086622 378023315 890058 477126060 14900711 1191393 511712433 35095827 204725 651796639 43378716 2018310 308442866 596282834 2328087 42294570 231322805 1602825 168464157 357054887 2277954 224671652 693289331 2062259 616695889 175688410 1253251 385431057 29127383 18...
output:
YES 503640380 7029894 503640380 1368652 686132608 7038782 686132608 890474 90378260 7044239 90378260 1135381 230910527 7117180 230910527 717420 62596222 7120722 62596222 454489 307408672 7133856 307408672 951464 553928329 7140520 553928329 1188014 118647522 7142376 118647522 1235695 692686592 714489...
result:
ok answer = 1
Test #18:
score: 0
Accepted
time: 62ms
memory: 7984kb
input:
40000 290669648 662085507 804601 669033554 119055358 638805 105668336 570987547 641107 70398923 679676225 1151529 67163601 217283316 655911 266292842 490670500 288695 332954119 213678087 316383 133514562 301390490 1150957 189198028 430695918 498385 52533444 508154472 662055 675557474 175423882 71076...
output:
YES 560511943 3500286 560511943 54446 588335785 3501863 588335785 167708 189086759 3506565 189086759 655520 203327533 3507611 203327533 672838 692808909 3519863 692808909 696483 87065466 3524317 87065466 661962 91333438 3529079 91333438 200794 525173361 3530632 525173361 27182 493589900 3532449 4935...
result:
ok answer = 1
Test #19:
score: 0
Accepted
time: 124ms
memory: 12892kb
input:
79806 675311888 175949323 45152 668303725 415877398 705454 526993355 106652475 101518 306843353 465414670 733685 235164634 54490010 250702 237718215 128806833 416572 47406184 660535125 231461 217980403 334240174 311035 438155656 608919183 741482 175786440 138973185 691587 383453409 420621369 23780 1...
output:
YES 271904806 2474196 271904806 34867 267180396 2474543 267180396 372647 438066890 2476476 438066890 28258 533939624 2478467 533939624 91266 595884202 2479225 595884202 317308 561625747 2483013 561625747 220972 507116963 2483117 507116963 96118 642842324 2484119 642842324 21282 128155699 2485854 128...
result:
ok answer = 1
Test #20:
score: 0
Accepted
time: 351ms
memory: 28668kb
input:
199809 330527920 105087498 120223 601378677 222559216 191284 604605920 449476822 241005 435487497 286817733 303877 682929431 10980946 280834 393289259 673421713 256371 217818174 324382996 403684 307178253 324362921 334561 321290021 314861063 288503 661144513 394874427 31218 664021225 319719526 14923...
output:
YES 566895342 1567690 566895342 113777 558844934 1568466 558844934 40949 452739821 1568903 452739821 35209 378988327 1569183 378988327 177551 667250128 1569262 667250128 63447 192659083 1569934 192659083 86489 363034226 1570463 363034226 202711 615272804 1570872 615272804 28672 410425210 1570903 410...
result:
ok answer = 1
Test #21:
score: 0
Accepted
time: 266ms
memory: 31696kb
input:
200000 500000000 500000000 450000000 950000002 500000000 1 950000002 500014137 1 950000001 500028274 1 950000000 500042412 1 949999998 500056549 1 949999996 500070686 1 949999994 500084823 1 949999991 500098961 1 949999988 500113098 1 949999984 500127235 1 949999980 500141372 1 949999975 500155510 1...
output:
YES 50000006 499922245 50000006 499908108 949999995 499929314 949999995 499915177 949999997 499943451 949999997 499929314 50000001 499950520 50000001 499936382 949999999 499957588 949999999 499943451 50000000 499964657 50000000 499950520 950000000 499971726 950000000 499957588 49999998 499978794 499...
result:
ok answer = 1
Test #22:
score: 0
Accepted
time: 196ms
memory: 53500kb
input:
200000 1666 1666 1666 6664 1666 1666 11662 1666 1666 16660 1666 1666 21658 1666 1666 26656 1666 1666 31654 1666 1666 36652 1666 1666 41650 1666 1666 46648 1666 1666 51646 1666 1666 56644 1666 1666 61642 1666 1666 66640 1666 1666 71638 1666 1666 76636 1666 1666 81634 1666 1666 86632 1666 1666 91630 1...
output:
YES 4998 1666 3332 1666 9996 1666 8330 1666 14994 1666 13328 1666 19992 1666 18326 1666 24990 1666 23324 1666 29988 1666 28322 1666 34986 1666 33320 1666 39984 1666 38318 1666 44982 1666 43316 1666 49980 1666 48314 1666 54978 1666 53312 1666 59976 1666 58310 1666 64974 1666 63308 1666 69972 1666 683...
result:
ok answer = 1
Test #23:
score: 0
Accepted
time: 402ms
memory: 55200kb
input:
200000 1276 2177 1666 6143 1271 1666 12177 1577 1666 17105 1415 1666 21414 1758 1666 27078 1291 1666 31751 1856 1666 36681 2166 1666 42165 1914 1666 46298 2207 1666 51434 1925 1666 56782 1717 1666 61708 1408 1666 66612 1280 1666 71599 2168 1666 76405 1971 1666 81489 1694 1666 86696 2187 1666 91352 1...
output:
YES 4477 1271 2942 2177 10511 1577 7809 1271 15439 1415 13843 1577 19748 1758 18771 1415 25412 1291 23080 1758 30085 1856 28744 1291 35015 2166 33417 1856 40499 1914 38347 2166 44632 2207 43831 1914 49768 1925 47964 2207 55116 1717 53100 1925 60042 1408 58448 1717 64946 1280 63374 1408 69933 2168 68...
result:
ok answer = 1
Test #24:
score: 0
Accepted
time: 276ms
memory: 53632kb
input:
200000 1666 1666 1666 6588 2534 1666 11510 3402 1666 16432 4270 1666 21354 5138 1666 26276 6005 1666 31198 6873 1666 36120 7741 1666 41043 8609 1666 45965 9477 1666 50887 10345 1666 55809 11213 1666 60731 12081 1666 65653 12949 1666 70575 13817 1666 75497 14684 1666 80419 15552 1666 85341 16420 1666...
output:
YES 4922 2534 3332 1666 9844 3402 8254 2534 14766 4270 13176 3402 19688 5138 18098 4270 24610 6005 23020 5138 29532 6873 27942 6005 34454 7741 32864 6873 39377 8609 37786 7741 44299 9477 42709 8609 49221 10345 47631 9477 54143 11213 52553 10345 59065 12081 57475 11213 63987 12949 62397 12081 68909 1...
result:
ok answer = 1
Test #25:
score: 0
Accepted
time: 80ms
memory: 10620kb
input:
200000 1666 1666 1666 1666 6664 1666 1666 11662 1666 1666 16660 1666 1666 21658 1666 1666 26656 1666 1666 31654 1666 1666 36652 1666 1666 41650 1666 1666 46648 1666 1666 51646 1666 1666 56644 1666 1666 61642 1666 1666 66640 1666 1666 71638 1666 1666 76636 1666 1666 81634 1666 1666 86632 1666 1666 91...
output:
YES 0 6664 0 1666 0 11662 0 6664 0 16660 0 11662 0 21658 0 16660 0 26656 0 21658 0 31654 0 26656 0 36652 0 31654 0 41650 0 36652 0 46648 0 41650 0 51646 0 46648 0 56644 0 51646 0 61642 0 56644 0 66640 0 61642 0 71638 0 66640 0 76636 0 71638 0 81634 0 76636 0 86632 0 81634 0 91630 0 86632 0 96628 0 9...
result:
ok answer = 1
Test #26:
score: 0
Accepted
time: 110ms
memory: 10636kb
input:
200000 1238 1279 1666 1911 6266 1666 1278 11483 1666 1657 16880 1666 1637 22064 1666 1629 26455 1666 2087 31415 1666 1150 36477 1666 2020 41228 1666 1277 46249 1666 1331 51188 1666 1274 56871 1666 1709 61810 1666 1509 66281 1666 1922 71932 1666 2188 76257 1666 1947 81675 1666 2124 86511 1666 1231 91...
output:
YES 245 6266 245 1279 0 11483 0 1279 0 16880 0 11483 0 22064 0 16880 0 26455 0 22064 421 31415 421 26455 0 36477 0 26455 354 41228 354 36477 0 46249 0 36477 0 51188 0 46249 0 56871 0 51188 43 61810 43 56871 0 66281 0 56871 256 71932 256 66281 522 76257 522 71932 281 81675 281 71932 458 86511 458 816...
result:
ok answer = 1
Test #27:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
2 1000000000 1000000000 1000000000 0 0 1
output:
YES 0 1000000000 0 0
result:
ok answer = 1
Test #28:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
2 1000000000 1000000000 500000000 0 1000000000 499999999
output:
YES 500000000 1000000000 499999999 1000000000
result:
ok answer = 1
Test #29:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
2 0 1000000000 499999999 0 0 500000000
output:
YES 0 1000000000 0 0
result:
ok answer = 1
Test #30:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
2 1000000000 1000000000 499999999 1000000000 0 500000000
output:
YES 500000001 1000000000 500000001 0
result:
ok answer = 1