QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488157 | #6639. Disk Tree | ucup-team052# | WA | 6ms | 4244kb | C++23 | 2.6kb | 2024-07-23 17:13:01 | 2024-07-23 17:13:01 |
Judging History
answer
#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=200005;
int n;
struct circ{
int x,y,r;
}a[N];
struct node{
int y,id,op;
bool operator<(const node&rhs){
if(y!=rhs.y)return y<rhs.y;
return a[id].x<a[rhs.id].x;
}
};
vector<array<int,4> >ans;
void push(int x1,int y1,int x2,int y2){
assert(0<=x1&&x1<=(int)1e9);
assert(0<=x2&&x2<=(int)1e9);
assert(0<=y1&&y1<=(int)1e9);
assert(0<=y2&&y2<=(int)1e9);
x1=max(x1,0),x1=min(x1,(int)1e9);
x2=max(x2,0),x2=min(x2,(int)1e9);
y1=max(y1,0),y1=min(y1,(int)1e9);
y2=max(y2,0),y2=min(y2,(int)1e9);
printf("%d %d %d %d\n",x1,y1,x2,y2);
}
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
rd(n);
vector<node>vec;
rep(i,1,n){
rd(a[i].x),rd(a[i].y),rd(a[i].r);
vec.pb((node){max(0,a[i].y-a[i].r),i,1});
vec.pb((node){min(int(1e9),a[i].y+a[i].r),i,-1});
}
sort(vec.begin(),vec.end());
set<pair<int,int> >S;
int last=-1;
puts("YES");
for(int i=0,j;i<SZ(vec);i=j){
// D("! y=%d\n",vec[i].y);
j=i+1;
while(j<SZ(vec)&&vec[i].y==vec[j].y)++j;
if(S.empty()){
int old=-1;
rep(k,i,j-1)if(vec[k].op==1){
if(old!=-1){
push(a[old].x,vec[i].y,a[vec[k].id].x,vec[i].y);
}
old=vec[k].id;
}
}else{
rep(k,i,j-1)if(vec[k].op==1){
auto it=S.lower_bound(make_pair(a[vec[k].id].x,-2e9));
if(it!=S.end()){
push(it->first,vec[i].y-1,a[vec[k].id].x,vec[i].y);
}else if(it!=S.begin()){
--it;
push(it->first,vec[i].y-1,a[vec[k].id].x,vec[i].y);
}
}
}
rep(k,i,j-1)if(vec[k].op==1){
if(S.empty()){
if(last!=-1){
push(a[last].x,min((int)1e9,a[last].y+a[last].r),a[vec[k].id].x,vec[i].y);
}
}
S.emplace(a[vec[k].id].x,vec[k].id);
}
if(!S.empty()){
last=S.begin()->second;
}
rep(k,i,j-1)if(vec[k].op==-1){
S.erase(make_pair(a[vec[k].id].x,vec[k].id));
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 4 10 4 1 3 0 4
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
2 1 1 1 3 3 1
output:
YES 1 1 3 2
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 2 0 10 0 10 0 20 0 10 18 3 19 10 18 20 19
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3772kb
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 0 0 34 0 0 13 17 14 17 26 29 27 17 34 28 45 28 57 48 58 48 71 17 72 48 76 99 77 48 77 45 78 99 84 98 85
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3716kb
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 47 0 307 0 307 0 447 0 447 0 572 0 572 0 743 0 743 0 981 0 981 1 819 2 981 28 865 29 981 69 897 70 307 70 205 71 572 80 448 81 205 81 133 82 572 81 482 82 981 107 951 108 47 108 8 109 482 136 225 137 951 145 975 146 225 147 137 148 482 160 422 161 422 164 412 165 743 166 822 167 412 167 290 168 ...
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3676kb
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 833 0 2381 0 2381 0 6112 0 6112 0 7051 0 7051 0 7552 0 7552 0 8844 0 6112 45 4163 46 7552 123 7251 124 6112 163 4278 164 8844 272 7602 273 6112 278 4775 279 7602 375 7300 376 833 441 147 442 4775 496 3446 497 4775 558 3918 559 3918 605 3731 606 3918 611 3897 612 3446 705 3427 706 4775 749 3984 7...
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 0ms
memory: 4016kb
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 17439 0 29077 0 29077 0 41631 0 41631 0 59944 0 59944 0 77261 0 77261 0 91690 0 77261 135 68592 136 91690 183 84713 184 59944 663 52006 664 17439 850 9204 851 29077 1065 24210 1066 91690 1116 98474 1117 77261 3561 70020 3562 9204 4212 3750 4213 41631 4638 30900 4639 29077 4759 27055 4760 17439 5...
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 1ms
memory: 3788kb
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 20680215 0 113708920 0 113708920 0 141987231 0 141987231 0 172728107 0 172728107 0 226080097 0 226080097 0 299841077 0 299841077 0 403214718 0 403214718 0 465961807 0 465961807 0 514663175 0 514663175 0 563659908 0 563659908 0 621861762 0 621861762 0 667862689 0 667862689 0 707624813 0 707624813...
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 2ms
memory: 3832kb
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 2252230 0 108950037 0 108950037 0 200843132 0 200843132 0 222298247 0 222298247 0 249529924 0 249529924 0 266200344 0 266200344 0 317125332 0 317125332 0 439494346 0 439494346 0 584847362 0 584847362 0 641324357 0 641324357 0 672822472 0 672822472 0 789192278 0 789192278 0 897276291 0 897276291 ...
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 4ms
memory: 4000kb
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 49536879 0 134578061 0 134578061 0 235794912 0 235794912 0 331201192 0 331201192 0 409421203 0 409421203 0 475690214 0 475690214 0 567189171 0 567189171 0 658173809 0 658173809 0 687354759 0 687354759 0 699032270 0 699032270 0 711414638 0 711414638 0 723543058 0 723543058 0 746470787 0 746470787...
result:
ok answer = 1
Test #11:
score: -100
Wrong Answer
time: 6ms
memory: 4244kb
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 8 0 893 0 893 0 1761 0 1761 0 1991 0 1991 0 2252 0 2252 0 2367 0 2367 0 2464 0 2464 0 2689 0 2689 0 2928 0 2928 0 3060 0 3060 0 3176 0 3176 0 3246 0 3246 0 3537 0 3537 0 3804 0 3804 0 4043 0 4043 0 4154 0 4154 0 5298 0 5298 0 6448 0 6448 0 6639 0 6639 0 6789 0 6789 0 6941 0 6941 0 7004 0 7004 0 ...
result:
wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks