QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114910 | #6639. Disk Tree | jeffqi | WA | 1ms | 3552kb | C++23 | 1.9kb | 2023-06-23 23:28:45 | 2023-06-23 23:28:47 |
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) {
cout << l << ' ' << r << ' ' << k << '\n';
}
auto col = prev(eit)->se;
for (auto it = bit; it != eit; it++) {
if (n == 100 && l == 453) {
cout << it->fi << ' ' << it->se.l << ' ' << it->se.r << ' ' << it->se.k << '\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) {
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: 1ms
memory: 3508kb
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: 3552kb
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: 0
Accepted
time: 1ms
memory: 3444kb
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: 3452kb
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 654 992 453 428 509 868 509 463 664 635 530 530 537 734 537 463 664 635 554 554 615 781 599 599 604 901 604 554 615 781 613 613 748 797 619 619 694 901 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...
result:
wrong answer Token parameter [name=YES or NO] equals to "453", doesn't correspond to pattern "[A-Za-z]+"