Submission #774269

#	Time	Username	Problem	Language	Result	Execution time	Memory
774269		xetrk	Circle selection (APIO18_circle_selection)	C++17	87 / 100	3048 ms	55804 KiB

circle_selection

#pragma warning(disable:4996)

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef long double ld;

int n;

vector<vector<ll>> circle;

vector<pair<ll, int>> sortRadius, sortX, sortY;


int ans[301000];
int parentX[300100], parentY[300100];
//int depthX[300100], depthY[300100];
int xIdx[300100], yIdx[300100];

int xCnt[1050000], yCnt[1050000];//세그먼트 트리

inline ll GetDist(ll x1, ll y1, ll x2, ll y2)
{
    // 아 좌표값 마이너스도 들어오네
    ll xx = max(x1, x2) - min(x1, x2);
    ll yy = max(y1, y2) - min(y1, y2);
    return (xx * xx) + (yy * yy);
}



bool comp(const pair<ll, int>& a, const pair<ll, int>& b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

bool compSort(const pair<ll, int>& a, const pair<ll, int>& b)
{
    if (a.first == b.first)
        return a.second < b.second;

    return a.first > b.first;
}


int find(int a, int parent[])
{
    if (parent[a] != a)
        parent[a] = find(parent[a], parent);
    return parent[a];
}

void merge(int a, int b, int parent[]) 
{
    a = find(a, parent), b = find(b, parent);
    if (a > b) swap(a, b);//b가더커야함
    parent[a] = b;//더큰걸부모로
}


int initSeg(int s, int e, int node, int tree[])
{
    if (s == e) return tree[node] = 1;
    int mid = (s + e) / 2;
    return tree[node] = initSeg(s, mid, node * 2, tree) + initSeg(mid + 1, e, node * 2 + 1, tree);
}

int sumSeg(int s, int e, int node, int left, int right, int tree[])
{
    if (left > e || right < s) return 0;

    //범위안에있으면
    if (left <= s && e <= right) return tree[node];

    int mid = (s + e) / 2;
    return sumSeg(s, mid, node * 2, left, right, tree) + sumSeg(mid + 1, e, node * 2 + 1, left, right, tree);
}

void minusSeg(int s, int e, int node, int index, int tree[])
{
    if (index<s || index>e) return;

    tree[node]--;
    if (s == e) return;
    int mid = (s + e) / 2;
    minusSeg(s, mid, node * 2, index, tree);
    minusSeg(mid + 1, e, node * 2 + 1, index, tree);
}


int main()
{
    ll x, y, r, r2;
    int i;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%lld %lld %lld", &x, &y, &r);
        //x = 1, y = 1, r = 3;
        circle.push_back({ x,y,r });
        sortRadius.push_back({ r,i });
        sortX.push_back({ x,i });
        sortY.push_back({ y,i });
        parentX[i] = parentY[i] = i;
        //depthX[i] = depthY[i] = 1;
    }

    sort(sortRadius.begin(), sortRadius.end(), compSort);
    sort(sortX.begin(), sortX.end());
    sort(sortY.begin(), sortY.end());


    for (int i = 0; i < n; i++)
    {
        xIdx[sortX[i].second] = i;
        yIdx[sortY[i].second] = i;
    }

    initSeg(0, n - 1, 1, xCnt);
    initSeg(0, n - 1, 1, yCnt);

    int cur, curcmp;
    int xMin, xMax, yMin, yMax;
    int next;
    ll rr;

    int j;


    fill(ans, ans + n + 2, -1);

    for (int curDelete = 0; curDelete < n; curDelete++)
    {
        cur = sortRadius[curDelete].second;
        if (ans[cur] != -1)
            continue;


        x = circle[cur][0], y = circle[cur][1], r = circle[cur][2];
        if (curDelete < n - 1)
            r2 = r + sortRadius[curDelete + 1].first + 1;
        else
            r2 = r * 2 + 1;

        // a이하를 찾아야하는데 lower bound는  a이상인걸 찾으니까.. 근데 그 이하인걸 찾아야하니 1빼줌
        xMin = lower_bound(sortX.begin(), sortX.end(), pair<ll, int>(x - r2, -1), comp) - sortX.begin();
        xMax = upper_bound(sortX.begin(), sortX.end(), pair<ll, int>(x + r2, 301000), comp) - sortX.begin();

        yMin = lower_bound(sortY.begin(), sortY.end(), pair<ll, int>(y - r2, -1), comp) - sortY.begin();
        yMax = upper_bound(sortY.begin(), sortY.end(), pair<ll, int>(y + r2, 301000), comp) - sortY.begin();

        xMin--;
        yMin--;

        if (xMin < 0) xMin = 0;
        if (yMin < 0) yMin = 0;

        if (xMin >= sortX.size()) xMin = sortX.size() - 1;
        if (yMin >= sortY.size()) yMin = sortY.size() - 1;
        if (xMax >= sortX.size()) xMax = sortX.size() - 1;
        if (yMax >= sortY.size()) yMax = sortY.size() - 1;

        //xMin = 0, yMin = 0, xMax = n - 1, yMax = n - 1;


        ans[cur] = cur;


        j = xIdx[cur];

        if (j - 1 >= 0 && ans[sortX[j - 1].second] != -1)
            merge(j, j - 1, parentX);
        if (j + 1 < n && ans[sortX[j + 1].second] != -1)
            merge(j, j + 1, parentX);
        minusSeg(0, n - 1, 1, j, xCnt);

        j = yIdx[cur];

        if (j - 1 >= 0 && ans[sortY[j - 1].second] != -1)
            merge(j, j - 1, parentY);
        if (j + 1 < n && ans[sortY[j + 1].second] != -1)
            merge(j, j + 1, parentY);
        minusSeg(0, n - 1, 1, j, yCnt);

        //xIdx[cur]

        int xRealCnt = sumSeg(0, n - 1, 1, xMin, xMax, xCnt);
        int yRealCnt = sumSeg(0, n - 1, 1, yMin, yMax, yCnt);



        if (xRealCnt < yRealCnt)
        {
            i = xMin;
            while (i <= xMax)
            {
                curcmp = sortX[i].second;
                
                if (ans[curcmp] != -1)
                {
                    i = find(i, parentX) + 1;
                    continue;
                }
                rr = r + circle[curcmp][2];
                if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
                {
                    ans[curcmp] = cur;
                    minusSeg(0, n - 1, 1, i, xCnt);

                    if (i - 1 >= 0 && ans[sortX[i - 1].second] != -1)
                        merge(i, i - 1, parentX);
                    if (i + 1 < n && ans[sortX[i + 1].second] != -1)
                        merge(i, i + 1, parentX);

                    j = yIdx[curcmp];
                    minusSeg(0, n - 1, 1, j, yCnt);

                    if (j - 1 >= 0 && ans[sortY[j - 1].second] != -1)
                        merge(j, j - 1, parentY);
                    if (j + 1 < n && ans[sortY[j + 1].second] != -1)
                        merge(j, j + 1, parentY);
                   
                }
                i = find(i, parentX) + 1;
            }
        }
        else
        {
            i = yMin;
            while (i <= yMax)
            {
                curcmp = sortY[i].second;
                if (ans[curcmp] != -1)
                {
                    i = find(i, parentY) + 1;
                    continue;
                }
                rr = r + circle[curcmp][2];
                if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
                {
                    ans[curcmp] = cur;
                    minusSeg(0, n - 1, 1, i, yCnt);

                    if (i - 1 >= 0 && ans[sortY[i - 1].second] != -1)
                        merge(i, i - 1, parentY);
                    if (i + 1 < n && ans[sortY[i + 1].second] != -1)
                        merge(i, i + 1, parentY);


                    j = xIdx[curcmp];
                    minusSeg(0, n - 1, 1, j, xCnt);

                    if (j - 1 >= 0 && ans[sortX[j - 1].second] != -1)
                        merge(j, j - 1, parentX);
                    if (j + 1 < n && ans[sortX[j + 1].second] != -1)
                        merge(j, j + 1, parentX);

                }
                i = find(i, parentY) + 1;
            }
            /*
            for (int i = yMax; i >= yMin; i--)
            {
             curcmp = sortY[i].second;
             if (ans[curcmp]!= -1) continue;
             rr = r + circle[curcmp][2];
             if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
             {
              ans[curcmp] = cur;
              //sortY.erase(sortY.begin() + i);
             }
            }*/
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", ans[i] + 1);

    return 0;
}

Compilation message (stderr)

circle_selection.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    1 | #pragma warning(disable:4996)
      | 
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         if (xMin >= sortX.size()) xMin = sortX.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:164:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         if (yMin >= sortY.size()) yMin = sortY.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:165:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         if (xMax >= sortX.size()) xMax = sortX.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         if (yMax >= sortY.size()) yMax = sortY.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:129:9: warning: unused variable 'next' [-Wunused-variable]
  129 |     int next;
      |         ^~~~
circle_selection.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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