QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123560#6639. Disk TreeinstallbWA 2ms11672kbC++142.7kb2023-07-12 21:06:532023-07-12 21:06:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 21:06:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11672kb
  • [2023-07-12 21:06:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400005;

struct interval{
    int l,r,pos,id;
    bool operator < (const interval &o)const{
        if(l == o.l) return pos < o.pos;
        return l < o.l;
    }
}s[N];

set <pair <int,int> > st;
vector <tuple <int,int,int,int> > ans;
int n,x[N],y[N],r[N];
pair <int,int> lis[N << 2]; int lsc = 0;

void solve(){
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> x[i] >> y[i] >> r[i];
        s[i] = {x[i] - r[i],x[i] + r[i],y[i],i};
    }
    sort(s + 1,s + 1 + n);
    // x has to be >= 0, so connect all possible circles with x = 0 first
    int pos = 0;
    for(int i = 1;i <= n;i ++){
        if(x[s[i].id] - r[s[i].id] <= 0) pos = i;
        else break;
    }
    vector <pair <int,int> > G;
    for(int i = 1;i <= pos;i ++){
        G.push_back({y[s[i].id],s[i].id});
        st.insert({y[s[i].id],s[i].id});
    }
    sort(G.begin(),G.end());
    for(int i = 1;i < G.size();i ++){
        int u = G[i - 1].second,v = G[i].second;
        ans.push_back({0,y[u],0,y[v]});
    }
    
    pair <int,int> mxr = {-1,-1};
    for(int i = 1;i <= pos;i ++) mxr = max(mxr,{x[s[i].id] + r[s[i].id],s[i].id});
    for(int i = pos + 1;i <= n;i ++){
        int u = s[i].id,id = -1;
        while(st.size()){
            auto it = st.lower_bound({y[u],-1});
            if(it == st.end()) break;
            int v = it->second;
            if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
            else{
                id = v;
                break;
            }
        }
        if(id == -1){
            while(st.size()){
                auto it = -- st.lower_bound({y[u],-1});
                int v = it->second;
                if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
                else{
                    id = v;
                    break;
                }
            }
        }
        if(id == -1 && i > 1) ans.push_back({mxr.first,y[mxr.second],x[u] - r[u],y[u]});
        else{
            lis[++ lsc] = {x[u] - r[u],y[id]};
            lis[++ lsc] = {x[u] - r[u],y[u]};
            // ans.push_back({x[u] - r[u],y[id],x[u] - r[u],y[u]});
        }
        st.insert({y[u],u});
        mxr = max(mxr,{x[u] + r[u],u});
    }
    sort(lis + 1,lis + 1 + lsc);
    lsc = unique(lis + 1,lis + 1 + lsc) - lis - 1;
    for(int i = 2;i <= lsc;i ++){
        if(lis[i].first == lis[i - 1].first) ans.push_back({lis[i - 1].first,lis[i - 1].second,lis[i].first,lis[i].second});
    }

    if(ans.size() != n - 1) cout << ans.size() << endl;
    cout << "YES\n";
    for(auto [a,b,c,d] : ans) cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9656kb

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
0 0 0 5
4 0 4 10

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 2ms
memory: 11600kb

input:

2
1 1 1
3 3 1

output:

YES
2 1 2 3

result:

ok answer = 1

Test #3:

score: 0
Accepted
time: 2ms
memory: 11672kb

input:

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

output:

YES
1 0 1 10
2 10 2 20
19 0 19 10
19 10 19 20

result:

ok answer = 1

Test #4:

score: 0
Accepted
time: 2ms
memory: 9548kb

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
58 68 88 95
7 8 7 24
7 24 7 82
18 55 18 82
24 0 24 24
27 29 27 55
35 55 35 88
38 68 38 88
95 81 95 95

result:

ok answer = 1

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 11616kb

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:

102
YES
0 13 0 179
0 179 0 366
0 366 0 520
0 520 0 663
0 663 0 773
7 773 7 952
20 607 20 663
39 843 39 952
60 703 60 773
63 850 63 952
64 226 64 366
75 790 75 850
81 208 81 226
100 115 100 208
111 603 111 703
120 512 120 603
129 156 129 366
134 241 134 366
176 100 176 241
179 703 179 934
198 323 198...

result:

wrong answer Token parameter [name=YES or NO] equals to "102", doesn't correspond to pattern "[A-Za-z]+"