Submission #217675

#	Time	Username	Problem	Language	Result	Execution time	Memory
217675		VEGAnn	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3092 ms	45948 KiB

circle_selection

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
using namespace std;
typedef long long ll;
const int N = 300100;
const int M = 200100;
const int oo = 2e9 + 7;
set<pii, greater<pii> > bst;
vector<int> xs;
int x[N], y[N], r[N], n, mrk[N], nm[N], obr[N];
pii st[2][4 * N], BAD = MP(-oo, -oo);

ll sqr(ll x){ return (x * x);}

bool cmp(int _x, int _y){
    return x[_x] < x[_y];
}

void build(int v, int l, int r1){
    if (l == r1){
        st[0][v] = MP(r[nm[l]] + x[nm[l]], nm[l]);
        st[1][v] = MP(r[nm[l]] - x[nm[l]], nm[l]);
        bst.insert(MP(r[nm[l]], -nm[l]));
        return;
    }

    int md = (l + r1) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r1);

    st[0][v] = max(st[0][v + v], st[0][v + v + 1]);
    st[1][v] = max(st[1][v + v], st[1][v + v + 1]);
}

void update(int v, int l, int r, int ps){
    if (l == r){
        st[0][v] = st[1][v] = BAD;
        return;
    }
    int md = (l + r) >> 1;

    if (ps <= md)
        update(v + v, l, md, ps);
    else update(v + v + 1, md + 1, r, ps);

    st[0][v] = max(st[0][v + v], st[0][v + v + 1]);
    st[1][v] = max(st[1][v + v], st[1][v + v + 1]);
}

pii get(int tp, int v, int tl, int tr, int l, int r){
    if (l > r) return BAD;
    if (tl == l && tr == r) return st[tp][v];

    int md = (tl + tr) >> 1;
    return max(get(tp, v + v, tl, md, l, min(r, md)),
               get(tp, v + v + 1, md + 1, tr, max(md + 1, l), r));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n;

    bool ok = 1;

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> r[i];
        xs.PB(x[i]);
        nm[i] = i;
        ok &= bool(y[i] == 0);
    }

    fill(mrk, mrk + n, -1);

    if (ok){
        sort(nm, nm + n, cmp);
        sort(all(xs));

        bst.clear();
        build(1, 0, n - 1);

        for (int i = 0; i < n; i++)
            obr[nm[i]] = i;

        while (sz(bst) > 0){
            pii CUR = (*bst.begin());
            bst.erase(bst.begin());
            int mx = CUR.ft, nm = -CUR.sd;
            mrk[nm] = nm;

            update(1, 0, n - 1, obr[nm]);

            int loc = lower_bound(all(xs), x[nm]) - xs.begin();

            while (1){
                pii cr = get(0, 1, 0, n - 1, 0, loc - 1);

                if (cr.ft < -r[nm] + x[nm]) break;

                bst.erase(MP(r[cr.sd], -cr.sd));
                mrk[cr.sd] = nm;
                update(1, 0, n - 1, cr.sd);
            }

            while (1){
                pii cr = get(1, 1, 0, n - 1, loc, n - 1);

                if (cr.ft < -r[nm] - x[nm]) break;

                bst.erase(MP(r[cr.sd], -cr.sd));
                mrk[cr.sd] = nm;
                update(1, 0, n - 1, cr.sd);
            }
        }

        for (int i = 0; i < n; i++)
            cout << mrk[i] + 1 << " ";
        return 0;
    }

    int kol = n;

    for (; kol > 0; ){
        int nom = -1, mx = -1;

        for (int i = 0; i < n; i++){
            if (mrk[i] >= 0) continue;

            if (r[i] > mx){
                mx = r[i];
                nom = i;
            }
        }

        for (int i = 0; i < n; i++){
            if (mrk[i] >= 0) continue;

            ll cur = sqr(x[i] - x[nom]) + sqr(y[i] - y[nom]) - sqr(r[i] + r[nom]);

            if (cur <= 0){
                mrk[i] = nom;
                kol--;
            }
        }
    }

    for (int i = 0; i < n; i++)
        cout << mrk[i] + 1 << " ";

    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:96:17: warning: unused variable 'mx' [-Wunused-variable]
             int mx = CUR.ft, nm = -CUR.sd;
                 ^~

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