QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114915 | #6639. Disk Tree | jeffqi | WA | 1ms | 3556kb | C++23 | 2.2kb | 2023-06-23 23:37:33 | 2023-06-23 23:37:36 |
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);
if (n == 100 && (l == 453 || r == 453)) {
cout << l << ' ' << r << ' ' << k << '\n';
}
auto col = prev(eit)->se;
for (auto it = bit; it != eit; it++) {
if (n == 100 && (l == 453 || r == 453)) {
cout << it->fi << ' ' << it->se.l << ' ' << it->se.r << ' ' << it->se.k << ' ' << (it->se.k != -1 && (it == bit || prev(it)->se.r <= it->se.l)) << '\n';
}
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) {
ans.pb({it->se.l,it->se.k,lst.r-1,lst.k});
if (n == 100) {
cout << lst.l << ' ' << lst.r << ' ' << lst.k << '\n';
cout << prev(it)->fi << ' ' << prev(it)->se.l << ' ' << prev(it)->se.r << ' ' << prev(it)->se.k << '\n';
cout << it->fi << ' ' << it->se.l << ' ' << it->se.r << ' ' << it->se.k << '\n';
}
}
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: 3556kb
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: 3412kb
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: 3556kb
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: 0ms
memory: 3512kb
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: 1ms
memory: 3524kb
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:
298 453 939 292 257 336 854 1 336 284 485 746 0 428 428 509 868 0 453 654 992 453 428 509 868 1 509 463 664 635 0 530 530 537 734 0 537 463 664 635 0 554 554 615 781 0 599 599 604 901 0 604 554 615 781 0 613 613 748 797 0 619 619 694 901 0 298 453 939 303 298 453 939 453 453 654 992 YES 406 40 406 2...
result:
wrong answer Token parameter [name=YES or NO] equals to "298", doesn't correspond to pattern "[A-Za-z]+"