QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488109 | #6639. Disk Tree | ucup-team052# | WA | 0ms | 4128kb | C++23 | 2.3kb | 2024-07-23 16:50:32 | 2024-07-23 16:50:32 |
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){
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]