QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114846 | #6639. Disk Tree | jeffqi | WA | 1ms | 3552kb | C++23 | 1.6kb | 2023-06-23 18:27:59 | 2023-06-23 18:28:01 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
using namespace std;
namespace qiqi {
struct Data {
int l,r,k;
Data(int l = 0,int r = 0,int k = -1):l(max(l,0)),r(r),k(k) {}
bool friend operator < (Data a,Data b) {
return a.k < b.k;
}
};
void main() {
int n; cin >> n;
vector<Data> a(n);
for (int i = 0; i < n; i++) {
int x,y,r;
cin >> x >> y >> r;
a[i] = Data(x-r,x+r,y);
}
sort(all(a));
map<int,Data> c; c[0] = Data();
vector<array<int,4>> ans;
for (auto [l,r,k]:a) {
auto bit = prev(c.upper_bound(l)),eit = c.upper_bound(r-1);
Data col = prev(eit)->se;
for (auto it = bit; it != eit; it++) {
int y = it->se.k;
if (y != -1 && (it == bit || prev(it)->se.r <= it->se.l)) {
int x = max(l,it->fi);
ans.pb({x,k,x,y});
}
}
c.erase(next(bit),eit);
c[l] = Data(l,r,k);
c.emplace(r,col);
}
Data lst;
for (auto it = c.begin(); it != c.end(); it++) {
if (it->se.k != -1) {
if (it != c.begin() && prev(it)->se.r <= it->se.l) {
ans.pb({it->fi,it->se.k,lst.r,lst.k});
}
lst = it->se;
}
}
cout << "YES\n";
for (auto [a,b,c,d]:ans) {
cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
qiqi::main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3552kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 5 0 0 4 10 4 0
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
2 1 1 1 3 3 1
output:
YES 2 3 2 1
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 10 1 0 19 10 19 0 19 20 19 10 2 20 2 10
result:
ok answer = 1
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3476kb
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 7 24 7 8 24 24 24 0 27 29 27 0 18 55 18 24 27 55 27 29 38 68 38 0 7 82 7 24 35 88 35 55 38 88 38 68 95 95 95 81 88 95 58 68
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