oj.uz

Submission #742326

# Submission time Handle Problem Language Result Execution time Memory
742326 2023-05-16T06:07:10 Z victor_gao Circle selection (APIO18_circle_selection) C++17
12 / 100
 1190 ms 61028 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,ans[N],X[N],Y[N],R[N];
set<pii>sl,sr;
vector<pair<pii,int> >all;
bool cmp(pair<pii,int>a,pair<pii,int>b){
    if (a.x.x!=b.x.x) return a.x.x>b.x.x;
    else return a.x.y<b.x.y;
}
signed main(){
  //  fast
    cin>>n;
    for (int i=1;i<=n;i++){
        int a,b,c; cin>>a>>b>>c;
        X[i]=a; Y[i]=b; R[i]=c;
        sl.insert(pii(a-c,i));
        sr.insert(pii(a+c,i));
        all.push_back({{c,i},a});
    }
    sort(all.begin(),all.end(),cmp);
    for (auto [tmp,p]:all){
        auto [r,i]=tmp;
        if (ans[i]) continue;
        ans[i]=i;
        sl.erase(pii(p-r,i));
        sr.erase(pii(p+r,i));
        if (!sl.empty()){
            auto it=sl.lower_bound(pii(p-r,0LL));
            while (it!=sl.end()&&(it->x)<=p+r){
                int now=(it->y); it=sl.erase(it);
                ans[now]=i;
                sr.erase(pii(X[now]+R[now],now));
            }
        }
        if (!sr.empty()){
            auto it=sr.lower_bound(pii(p-r,0LL));
            while (it!=sr.end()&&(it->x)<=p+r){
                int now=(it->y); it=sr.erase(it);
                ans[now]=i;
                sl.erase(pii(X[now]-R[now],now));
            }
        }
    }
    for (int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<'\n';
}
/*
5
2 0 5
1 0 1
19 0 10
3 0 2
5 0 1
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1115 ms 56400 KB Output is correct
2 Correct 1100 ms 56460 KB Output is correct
3 Correct 1190 ms 56204 KB Output is correct
4 Correct 1120 ms 56368 KB Output is correct
5 Correct 874 ms 56208 KB Output is correct
6 Correct 926 ms 60872 KB Output is correct
7 Correct 901 ms 60976 KB Output is correct
8 Correct 871 ms 61028 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 928 ms 55992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -