QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488157#6639. Disk Treeucup-team052#WA 6ms4244kbC++232.6kb2024-07-23 17:13:012024-07-23 17:13:01

Judging History

你现在查看的是最新测评结果

  • [2024-07-23 17:13:01]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:4244kb
  • [2024-07-23 17:13:01]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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