QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136051 | #6639. Disk Tree | Delay_for_five_minutes | WA | 1ms | 3460kb | C++20 | 1.9kb | 2023-08-06 20:18:36 | 2023-08-06 20:18:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct ev {
int x , p;
int s; ///1 in , -1 out
int id;
};
bool operator < (ev a,ev b)
{
if(a.p == b.p) return a.s > b.s;
return a.p < b.p;
}
multiset<ev> st;
set<pair<int,int> > cur ; ///x_pos , id
struct line {
int x1,y1,x2,y2;
};
vector<line> ans;
int main()
{
// freopen("in.txt","r",stdin);
// ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
cin >> n;
for(int i =1;i <= n;i++) {
int x , y , r;cin >> x >> y >> r;
int l = max(0 , y - r) , R = min(1000000000 , y + r);
st.insert((ev){x , l , 1 , i}) ;
st.insert((ev){x , R , -1 , i});
}
int lsp = -1 , ls_s = -2;
vector<ev> now;
int lx = -1 , ly = -1;
st.insert((ev){0 , 1000000001 , 1 , 0});
for(auto &E : st) {
if((E.p != lsp || E.s != ls_s) && ls_s == 1) {
sort(now.begin() , now.end());
for(auto & cur_e : now) {
if(!cur.size()) {
if(lx != -1) ans.push_back((line){lx , ly , cur_e.x , cur_e.p });
}
else {
//printf("add2\n");
auto it = cur.lower_bound(pair<int,int>{cur_e.x , 0}) ;
if(it == cur.end()) it--;
ans.push_back((line){it->first , cur_e.p , cur_e.x , cur_e.p });
}
cur.insert(pair<int,int>{cur_e.x , cur_e.id });
}
now.clear();
}
if(E.s == 1) {
now.push_back(E) ;
}
else {
cur.erase(pair<int,int>{E.x , E.id });
lx = E.x ; ly = E.p;
}
lsp = E.p ; ls_s = E.s;
}
cout << "YES\n";
for(auto &s : ans) cout << s.x1 <<' ' << s.y1 <<' ' << s.x2 <<' ' << s.y2 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3452kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 1 3 10 4 10 4 0 4
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
2 1 1 1 3 3 1
output:
YES 1 2 3 2
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 10 0 2 0 10 0 20 0 10 19 20 19 10 19 3 19
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3456kb
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 14 17 14 17 27 29 27 17 34 28 45 28 58 48 58 48 72 17 72 48 77 99 77 48 78 45 78 99 85 98 85
result:
ok answer = 1
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3460kb
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 307 0 743 0 743 0 981 0 307 0 47 0 743 0 572 0 572 0 447 0 981 2 819 2 981 29 865 29 981 70 897 70 307 71 205 71 572 81 448 81 205 82 133 82 572 82 482 82 981 108 951 108 47 109 8 109 482 137 225 137 951 146 975 146 225 148 137 148 482 161 422 161 422 165 412 165 743 167 822 167 412 168 290 168 ...
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