Submission #487122

#	Time	Username	Problem	Language	Result	Execution time	Memory
487122		Redhood	Circle selection (APIO18_circle_selection)	C++14	19 / 100	3095 ms	233832 KiB

circle_selection

#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;

//const int N = (int)3e5 + 10;

//struct seg{
//    int a[4*N];
//    int p[4*N];
//    void clr(int x){
//        fill(a , a + 4 * N , x);
//        fill(p , p + 4 * N , x);
//    }
//    void push(int v){
//
//    }
//    int get(int v , int tl , int tr , int l , int r){
//        if(tl == l && tr == r){
//            return a[v];
//        }
//        int mid = (tl + tr) >> 1 , v1 = v << 1;
//        push(v);
//
//    }
//};
vector < array < int , 3 > > c;
bool intersec(int i , int j){
    if(1ll * (c[i][2] + c[j][2]) * (c[i][2] + c[j][2]) >= 1ll * (c[i][0]-c[j][0])*(c[i][0]-c[j][0])
                                                                + 1ll * (c[i][1]-c[j][1])*(c[i][1]-c[j][1])){
            return true;
    }
    return false;
}
const int N = (int)3e5 * 2;

vector < int > ans;
struct SEG{
    vector < int > lst[4*N];

    void add(int v , int tl , int tr , int pos , int val){
        lst[v].pb(val);
        if(tl == tr)return;
        int mid = (tl + tr) >> 1 , v1 = v << 1;
        if(pos <= mid)
            add(v1 , tl , mid , pos , val);
        else
            add(v1 | 1,  mid + 1 , tr , pos, val);
    }
    void dlt(int v , int tl , int tr , int l , int r, int X){
        if(tl == l && tr ==r){
            for(auto &u : lst[v]){
                if(ans[u] == -1)
                    ans[u] = X;
            }
            lst[v].clear();
            return;
        }
        int mid = (tl + tr) >> 1 , v1 = v << 1;
        if(l <=mid)
            dlt(v1 , tl , mid , l , min(r , mid) , X);
        if(r > mid)
            dlt(v1 | 1, mid + 1,  tr, max(l , mid + 1) , r, X);

    }
}L, R;
signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;

    c.resize(n);


    for(auto &i : c)
        cin >> i[0] >> i[1] >> i[2];


    bool Y = 1;
    for(auto &i : c)
        if(i[1] != 0)
            Y = 0;


    vector < int > p(n);
    iota(all(p) , 0);


    sort(all(p) , [&](int i , int j){
            if(c[i][2] == c[j][2]){
                return i < j;
         }
            return c[i][2] > c[j][2];
         });



    ans.resize(n , -1);

    if(Y){


        /// addd this shit


        vector < int > l(n) , r(n);
        vector < int > dots;
        for(int i = 0 ; i < n; ++i){
            l[i] = c[i][0] - c[i][2];
            r[i] = c[i][0] + c[i][2];
            dots.pb(l[i]);
            dots.pb(r[i]);

        }
        sort(all(dots));
        dots.erase(unique(all(dots)) , dots.end());

        /// zip it fuckvector < int > dots;

        for(int i = 0 ; i < n; ++i){
            l[i] = lower_bound(all(dots) , l[i]) - dots.begin();
            r[i] = lower_bound(all(dots) , r[i]) - dots.begin();


            R.add(1 , 0, N-1, r[i], i);
            L.add(1 , 0 , N-1 , l[i] , i);
        }

        for(int i : p){
            if(ans[i] != -1){
                continue;
            }
            R.dlt(1 , 0 , N- 1 , l[i],  r[i], i);
            L.dlt(1 , 0 , N - 1,  l[i] , r[i],  i);
        }

    }else{
    for(int i = 0 ; i < n; ++i){
        int bst = -1;
        for(int j = 0 ; j < i; ++j){
            if(ans[p[j]] == -1 && intersec(p[i], p[j])){
                bst = p[j];
                break;
            }
        }
        ans[p[i]] = bst;
    }

    }

    for(int i = 0; i < n; ++i){
        if(ans[i] == -1){
            cout << i + 1 << ' ';
        }else
            cout << ans[i] + 1 << ' ';
    }





    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7


1 1 1
100000000 1 1 1
1


11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1



*/

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13