QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123573 | #6639. Disk Tree | installb | WA | 146ms | 32700kb | C++14 | 4.2kb | 2023-07-12 21:51:29 | 2023-07-12 21:51:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400005;
struct interval{
int l,r,pos,id;
bool operator < (const interval &o)const{
if(l == o.l) return pos < o.pos;
return l < o.l;
}
}s[N];
set <pair <int,int> > st;
vector <tuple <int,int,int,int> > ans;
int n,x[N],y[N],r[N];
struct node{
int x,y,id;
bool operator < (const node &nd)const{
if(x == nd.x) return y < nd.y;
return x < nd.x;
}
};
// node lis[N << 2]; int lsc = 0;
vector <node> nx[N];
void solve(){
cin >> n;
int minl = 0x3f3f3f3f;
for(int i = 1;i <= n;i ++){
cin >> x[i] >> y[i] >> r[i];
s[i] = {x[i] - r[i],x[i] + r[i],y[i],i};
minl = min(minl,x[i] - r[i]);
}
if(minl < 0) minl = 0;
sort(s + 1,s + 1 + n);
// connect all possible circles with x = minl first
int pos = 0;
for(int i = 1;i <= n;i ++){
if(x[s[i].id] - r[s[i].id] <= minl) pos = i;
else break;
}
vector <pair <int,int> > G;
for(int i = 1;i <= pos;i ++){
G.push_back({y[s[i].id],s[i].id});
st.insert({y[s[i].id],s[i].id});
}
sort(G.begin(),G.end());
for(int i = 1;i < G.size();i ++){
int u = G[i - 1].second,v = G[i].second;
ans.push_back({0,y[u],0,y[v]});
}
G.clear();
pair <int,int> mxr = {-1,-1};
for(int i = 1;i <= pos;i ++) mxr = max(mxr,{x[s[i].id] + r[s[i].id],s[i].id});
for(int i = pos + 1;i <= n;i ++){
int u = s[i].id,id = -1;
if(i > 1 && x[s[i].id] - r[s[i].id] != x[s[i - 1].id] - r[s[i - 1].id]){
for(auto pi : G) st.insert(pi);
G.clear();
}
while(st.size()){
auto it = st.lower_bound({y[u],-1});
if(it == st.end()) break;
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v;
break;
}
}
if(id == -1){
while(st.size()){
auto it = -- st.lower_bound({y[u],-1});
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v;
break;
}
}
}
if(id == -1 && i > 1){
ans.push_back({mxr.first,y[mxr.second],x[u] - r[u],y[u]});
}
else{
nx[id].push_back({x[u] - r[u],y[u],u});
// lis[++ lsc] = {x[u] - r[u],min(y[id],y[u]),max(y[id],y[u])};
// ans.push_back({x[u] - r[u],y[id],x[u] - r[u],y[u]});
}
G.push_back({y[u],u});
mxr = max(mxr,{x[u] + r[u],u});
}
for(int i = 1;i <= n;i ++){
if(nx[i].size() == 0) continue;
sort(nx[i].begin(),nx[i].end());
int las = 0;
for(int j = 0;j < nx[i].size();j ++){
if(j + 1 == nx[i].size() || (nx[i][j].x != nx[i][j + 1].x)){
G.clear();
for(int k = las;k <= j;k ++){
G.push_back({nx[i][k].y,nx[i][k].id});
}
G.push_back({y[i],i});
sort(G.begin(),G.end());
for(int k = 1;k < G.size();k ++){
ans.push_back({nx[i][j].x,G[k - 1].first,nx[i][j].x,G[k].first});
}
las = j + 1;
}
}
}
// sort(lis + 1,lis + 1 + lsc);
// vector <int> H;
// for(int my = -1,i = 1;i <= lsc;i ++){
// H.push_back(lis[i].yl); H.push_back(lis[i].yr);
// my = max(my,lis[i].yr);
// if(i == lsc || lis[i + 1].x != lis[i].x || lis[i + 1].yl > my){
// sort(H.begin(),H.end());
// H.erase(unique(H.begin(),H.end()),H.end());
// for(int j = 1;j < H.size();j ++) ans.push_back({lis[i].x,H[j - 1],lis[i].x,H[j]});
// my = 0; H.clear();
// }
// }
if(ans.size() != n - 1) cout << ans.size() << endl;
cout << "YES\n";
for(auto [a,b,c,d] : ans) cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 18064kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 0 0 5 4 0 4 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 19288kb
input:
2 1 1 1 3 3 1
output:
YES 2 1 2 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 18024kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 0 1 10 2 10 2 20 19 0 19 10 19 10 19 20
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 17560kb
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 58 68 88 95 27 29 27 55 35 55 35 88 18 55 18 82 38 68 38 88 7 8 7 24 7 24 7 82 95 81 95 95 24 0 24 24
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 4ms
memory: 19340kb
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 0 13 0 179 0 179 0 366 0 366 0 520 0 520 0 663 0 663 0 773 488 714 488 783 927 697 927 914 977 709 977 914 406 40 406 265 420 163 420 265 432 132 432 265 498 190 498 265 260 710 260 854 284 746 284 854 312 265 312 438 366 422 366 438 530 734 530 992 554 781 554 992 599 901 599 992 613 797 613 99...
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 4ms
memory: 19504kb
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 0 1148 0 2852 0 2852 0 4653 0 4653 0 6162 0 6162 0 7670 2778 7991 2778 9798 2899 8690 2899 9798 2941 8806 2941 9798 3287 9131 3287 9798 3890 587 3890 647 1109 1326 1109 2717 4363 6830 4363 6858 55 7670 55 7903 178 7484 178 7670 7188 187 7188 1213 7384 110 7384 1213 7525 350 7525 1213 7948 424 79...
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 0ms
memory: 19396kb
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 0 16007 0 24419 0 24419 0 39900 0 39900 0 58648 0 58648 0 69461 0 69461 0 79893 0 79893 0 99921 48087 16699 48087 21821 49704 19338 49704 21821 7383 75412 7383 81086 47746 21821 47746 22290 37718 30750 37718 46942 38270 38309 38270 46942 39854 35058 39854 46942 42720 37079 42720 46942 47099 3780...
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 1ms
memory: 18988kb
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 0 93982006 0 235938924 0 235938924 0 359002653 0 359002653 0 429721563 0 429721563 0 500334319 0 500334319 0 553121854 0 553121854 0 595275379 0 595275379 0 673089475 0 673089475 0 713751639 0 713751639 0 769665792 0 769665792 0 816264930 0 816264930 0 918989948 486240692 170833760 486240692 246...
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 0ms
memory: 18984kb
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 0 4543545 0 20450809 0 20450809 0 33689791 0 33689791 0 73749521 0 73749521 0 85019332 0 85019332 0 91838752 0 91838752 0 115835530 0 115835530 0 138290805 0 138290805 0 244652455 0 244652455 0 344420182 0 344420182 0 372703679 0 372703679 0 411886099 0 411886099 0 433135538 0 433135538 0 493352...
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 9ms
memory: 17988kb
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 0 7669779 0 82305277 0 82305277 0 104534031 0 104534031 0 133505889 0 133505889 0 145494976 0 145494976 0 178650168 0 178650168 0 204712391 0 204712391 0 221426602 0 221426602 0 245488837 0 245488837 0 288398415 0 288398415 0 323305633 0 323305633 0 328807797 0 328807797 0 340684446 0 340684446 ...
result:
ok answer = 1
Test #11:
score: 0
Accepted
time: 11ms
memory: 18744kb
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 0 8 0 71 0 71 0 616 0 616 0 1146 0 1146 0 1314 0 1314 0 1592 0 1592 0 1751 0 1751 0 1799 0 1799 0 1883 0 1883 0 2188 0 2188 0 2481 0 2481 0 2550 0 2550 0 2631 0 2631 0 2676 0 2676 0 2756 0 2756 0 2887 0 2887 0 3106 0 3106 0 3323 0 3323 0 3437 0 3437 0 3584 0 3584 0 3695 0 3695 0 3784 0 3784 0 38...
result:
ok answer = 1
Test #12:
score: 0
Accepted
time: 62ms
memory: 24460kb
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 0 16414678 0 114863446 0 114863446 0 266626847 0 266626847 0 304414580 0 304414580 0 312730895 0 312730895 0 333397542 0 333397542 0 427209090 0 427209090 0 571603990 0 571603990 0 616424636 0 616424636 0 643298905 0 643298905 0 646455574 0 646455574 0 674631883 0 674631883 0 707448235 0 7074482...
result:
ok answer = 1
Test #13:
score: 0
Accepted
time: 146ms
memory: 29128kb
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 0 36450043 0 65503887 0 65503887 0 103165813 0 103165813 0 113223272 0 113223272 0 121163888 0 121163888 0 231691420 0 231691420 0 240450858 0 240450858 0 271364932 0 271364932 0 287867208 0 287867208 0 359415760 0 359415760 0 407335778 0 407335778 0 442225971 0 442225971 0 541026964 0 541026964...
result:
ok answer = 1
Test #14:
score: 0
Accepted
time: 139ms
memory: 29720kb
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 0 23586061 0 29081244 0 29081244 0 49313954 0 49313954 0 61288319 0 61288319 0 72741002 0 72741002 0 84962436 0 84962436 0 136092710 0 136092710 0 160263492 0 160263492 0 168474053 0 168474053 0 218635420 0 218635420 0 266233086 0 266233086 0 301197220 0 301197220 0 333616539 0 333616539 0 40477...
result:
ok answer = 1
Test #15:
score: 0
Accepted
time: 124ms
memory: 30300kb
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 0 31640168 0 94878040 0 94878040 0 114673404 0 114673404 0 133976538 0 133976538 0 138021782 0 138021782 0 144473048 0 144473048 0 175463994 0 175463994 0 179592469 0 179592469 0 219985608 0 219985608 0 230772950 0 230772950 0 287768048 0 287768048 0 292509612 0 292509612 0 305761966 0 305761966...
result:
ok answer = 1
Test #16:
score: 0
Accepted
time: 140ms
memory: 30976kb
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 0 741 0 1577 0 1577 0 2446 0 2446 0 4749 0 4749 0 5324 0 5324 0 5611 0 5611 0 6345 0 6345 0 6864 0 6864 0 7242 0 7242 0 8059 0 8059 0 8857 0 8857 0 9037 0 9037 0 10569 0 10569 0 11176 0 11176 0 11733 0 11733 0 12650 0 12650 0 13395 0 13395 0 14154 0 14154 0 15268 0 15268 0 15959 0 15959 0 16828 ...
result:
ok answer = 1
Test #17:
score: 0
Accepted
time: 12ms
memory: 18752kb
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 0 1053491 0 21950698 0 21950698 0 29071213 0 29071213 0 42350620 0 42350620 0 63221024 0 63221024 0 70529176 0 70529176 0 84344160 0 84344160 0 98466030 0 98466030 0 112841976 0 112841976 0 119439557 0 119439557 0 126486661 0 126486661 0 140952914 0 140952914 0 147195943 0 147195943 0 169069673 ...
result:
ok answer = 1
Test #18:
score: 0
Accepted
time: 19ms
memory: 19968kb
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 0 3898576 0 7023791 0 7023791 0 10876184 0 10876184 0 14518390 0 14518390 0 21171278 0 21171278 0 24950417 0 24950417 0 32148027 0 32148027 0 35669373 0 35669373 0 38900667 0 38900667 0 42087876 0 42087876 0 49175832 0 49175832 0 60111997 0 60111997 0 66792042 0 66792042 0 70483357 0 70483357 0 ...
result:
ok answer = 1
Test #19:
score: 0
Accepted
time: 57ms
memory: 23544kb
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 0 75115 0 2564757 0 2564757 0 4991138 0 4991138 0 7654178 0 7654178 0 10139465 0 10139465 0 12492643 0 12492643 0 14967837 0 14967837 0 22579503 0 22579503 0 25102875 0 25102875 0 27269094 0 27269094 0 32493546 0 32493546 0 34714044 0 34714044 0 39684135 0 39684135 0 47142938 0 47142938 0 498779...
result:
ok answer = 1
Test #20:
score: 0
Accepted
time: 143ms
memory: 32180kb
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 0 79477 0 3267733 0 3267733 0 4869837 0 4869837 0 6431437 0 6431437 0 8038686 0 8038686 0 11030533 0 11030533 0 14113479 0 14113479 0 18833700 0 18833700 0 20491240 0 20491240 0 23496141 0 23496141 0 26723859 0 26723859 0 29974279 0 29974279 0 31364131 0 31364131 0 34694473 0 34694473 0 36263968...
result:
ok answer = 1
Test #21:
score: -100
Wrong Answer
time: 120ms
memory: 32700kb
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 0 499978794 0 499992931 0 499992931 0 500007069 0 500007069 0 500021206 50000004 499922245 50000004 500000000 50000004 500000000 50000004 500077755 50000009 499893971 50000009 500000000 50000009 500000000 50000009 500106029 50000013 499879833 50000013 500000000 50000013 500000000 50000013 500120...
result:
wrong answer Two disks cannot reach eachother