QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488109#6639. Disk Treeucup-team052#WA 0ms4128kbC++232.3kb2024-07-23 16:50:322024-07-23 16:50:32

Judging History

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

  • [2024-07-23 16:50:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4128kb
  • [2024-07-23 16:50:32]
  • 提交

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){
	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){a[i].y-a[i].r,i,1});
		vec.pb((node){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;
			}
		}
		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(S.empty()){
				if(last!=-1){
					push(a[last].x,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: 4128kb

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: 3764kb

input:

2
1 1 1
3 3 1

output:

YES
1 1 3 2

result:

ok answer = 1

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3688kb

input:

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

output:

YES
2 -1 20 -1
20 -1 10 0
10 18 3 19
10 18 20 19

result:

wrong answer Integer element x_1,y_1,x_2,y_2[2] equals to -1, violates the range [0, 10^9]