QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114848 | #6639. Disk Tree | jeffqi | WA | 1ms | 3472kb | C++23 | 1.6kb | 2023-06-23 18:37:29 | 2023-06-23 18:37:30 |
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[-1] = Data();
vector<array<int,4>> ans;
for (auto [l,r,k]:a) {
auto bit = prev(c.lower_bound(l)),eit = c.upper_bound(r);
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: 0
Wrong Answer
time: 1ms
memory: 3472kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 4 10 4 0
result:
wrong output format Unexpected end of file - int32 expected