oj.uz

Submission #487122

# Submission time Handle Problem Language Result Execution time Memory
487122 2021-11-14T13:25:03 Z Redhood Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 233832 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 112988 KB Output is correct
2 Correct 50 ms 112892 KB Output is correct
3 Correct 51 ms 113004 KB Output is correct
4 Correct 48 ms 113004 KB Output is correct
5 Correct 56 ms 112924 KB Output is correct
6 Correct 60 ms 112964 KB Output is correct
7 Correct 53 ms 112964 KB Output is correct
8 Correct 50 ms 113008 KB Output is correct
9 Correct 48 ms 113008 KB Output is correct
10 Correct 53 ms 112964 KB Output is correct
11 Correct 50 ms 112956 KB Output is correct
12 Correct 51 ms 112912 KB Output is correct
13 Correct 49 ms 112920 KB Output is correct
14 Correct 52 ms 112940 KB Output is correct
15 Correct 48 ms 112980 KB Output is correct
16 Correct 51 ms 113024 KB Output is correct
17 Correct 50 ms 112948 KB Output is correct
18 Correct 52 ms 112924 KB Output is correct
19 Correct 56 ms 113036 KB Output is correct
20 Correct 54 ms 113036 KB Output is correct
21 Correct 53 ms 113096 KB Output is correct
22 Correct 103 ms 113116 KB Output is correct
23 Correct 104 ms 113176 KB Output is correct
24 Correct 105 ms 113092 KB Output is correct
25 Correct 99 ms 113120 KB Output is correct
26 Correct 103 ms 113088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 219048 KB Output is correct
2 Correct 1372 ms 223040 KB Output is correct
3 Correct 1389 ms 222160 KB Output is correct
4 Correct 1236 ms 219568 KB Output is correct
5 Correct 1082 ms 209328 KB Output is correct
6 Correct 1438 ms 233832 KB Output is correct
7 Correct 1478 ms 226136 KB Output is correct
8 Correct 1409 ms 229788 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 113000 KB Output is correct
2 Execution timed out 3095 ms 114900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3095 ms 118848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 112988 KB Output is correct
2 Correct 50 ms 112892 KB Output is correct
3 Correct 51 ms 113004 KB Output is correct
4 Correct 48 ms 113004 KB Output is correct
5 Correct 56 ms 112924 KB Output is correct
6 Correct 60 ms 112964 KB Output is correct
7 Correct 53 ms 112964 KB Output is correct
8 Correct 50 ms 113008 KB Output is correct
9 Correct 48 ms 113008 KB Output is correct
10 Correct 53 ms 112964 KB Output is correct
11 Correct 50 ms 112956 KB Output is correct
12 Correct 51 ms 112912 KB Output is correct
13 Correct 49 ms 112920 KB Output is correct
14 Correct 52 ms 112940 KB Output is correct
15 Correct 48 ms 112980 KB Output is correct
16 Correct 51 ms 113024 KB Output is correct
17 Correct 50 ms 112948 KB Output is correct
18 Correct 52 ms 112924 KB Output is correct
19 Correct 56 ms 113036 KB Output is correct
20 Correct 54 ms 113036 KB Output is correct
21 Correct 53 ms 113096 KB Output is correct
22 Correct 103 ms 113116 KB Output is correct
23 Correct 104 ms 113176 KB Output is correct
24 Correct 105 ms 113092 KB Output is correct
25 Correct 99 ms 113120 KB Output is correct
26 Correct 103 ms 113088 KB Output is correct
27 Correct 60 ms 113220 KB Output is correct
28 Correct 55 ms 113212 KB Output is correct
29 Correct 58 ms 113208 KB Output is correct
30 Correct 249 ms 113192 KB Output is correct
31 Correct 257 ms 113204 KB Output is correct
32 Correct 247 ms 113208 KB Output is correct
33 Correct 94 ms 115576 KB Output is correct
34 Correct 97 ms 115476 KB Output is correct
35 Correct 433 ms 115584 KB Output is correct
36 Execution timed out 3090 ms 114884 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 112988 KB Output is correct
2 Correct 50 ms 112892 KB Output is correct
3 Correct 51 ms 113004 KB Output is correct
4 Correct 48 ms 113004 KB Output is correct
5 Correct 56 ms 112924 KB Output is correct
6 Correct 60 ms 112964 KB Output is correct
7 Correct 53 ms 112964 KB Output is correct
8 Correct 50 ms 113008 KB Output is correct
9 Correct 48 ms 113008 KB Output is correct
10 Correct 53 ms 112964 KB Output is correct
11 Correct 50 ms 112956 KB Output is correct
12 Correct 51 ms 112912 KB Output is correct
13 Correct 49 ms 112920 KB Output is correct
14 Correct 52 ms 112940 KB Output is correct
15 Correct 48 ms 112980 KB Output is correct
16 Correct 51 ms 113024 KB Output is correct
17 Correct 50 ms 112948 KB Output is correct
18 Correct 52 ms 112924 KB Output is correct
19 Correct 56 ms 113036 KB Output is correct
20 Correct 54 ms 113036 KB Output is correct
21 Correct 53 ms 113096 KB Output is correct
22 Correct 103 ms 113116 KB Output is correct
23 Correct 104 ms 113176 KB Output is correct
24 Correct 105 ms 113092 KB Output is correct
25 Correct 99 ms 113120 KB Output is correct
26 Correct 103 ms 113088 KB Output is correct
27 Correct 1306 ms 219048 KB Output is correct
28 Correct 1372 ms 223040 KB Output is correct
29 Correct 1389 ms 222160 KB Output is correct
30 Correct 1236 ms 219568 KB Output is correct
31 Correct 1082 ms 209328 KB Output is correct
32 Correct 1438 ms 233832 KB Output is correct
33 Correct 1478 ms 226136 KB Output is correct
34 Correct 1409 ms 229788 KB Output is correct
35 Correct 51 ms 113000 KB Output is correct
36 Execution timed out 3095 ms 114900 KB Time limit exceeded
37 Halted 0 ms 0 KB -