QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114909 | #6639. Disk Tree | jeffqi | WA | 1ms | 3512kb | C++23 | 1.7kb | 2023-06-23 23:21:26 | 2023-06-23 23:21:29 |
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+1,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.upper_bound(l)),eit = c.lower_bound(r);
auto 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;
c.erase(c.begin());
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) {
if (n == 100) {
cout << it->se.l << ' ' << lst.r-1 << '\n';
}
ans.pb({it->se.l,it->se.k,lst.r-1,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: 0ms
memory: 3512kb
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: 1ms
memory: 3452kb
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: 3492kb
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: 0
Accepted
time: 1ms
memory: 3448kb
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 24 18 55 18 24 38 68 38 55 7 82 7 24 35 88 35 55 95 95 95 81 88 95 58 68
result:
ok answer = 1
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3456kb
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:
453 452 YES 406 40 406 21 881 52 881 11 891 76 891 11 445 84 445 40 807 97 807 14 842 97 842 52 207 100 207 21 100 115 100 13 432 132 432 40 506 132 506 58 927 132 927 11 968 153 968 132 129 156 129 115 201 161 201 100 420 163 420 40 0 179 0 13 806 183 806 97 498 190 498 132 254 204 254 21 896 204 8...
result:
wrong answer Token parameter [name=YES or NO] equals to "453", doesn't correspond to pattern "[A-Za-z]+"