oj.uz

Submission #260426

# Submission time Handle Problem Language Result Execution time Memory
260426 2020-08-10T08:53:51 Z Kastanda Circle selection (APIO18_circle_selection) C++11
38 / 100
 2156 ms 406476 KB 
// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005;
int n, X[N], Y[N], R[N], M[N];
vector < int > UX, UY;
vector < pair < int , int > > V[N * 2];
set < pair < int , int > > ST[N * 2];
inline int GetId(int a, vector < int > &U)
{
        return (int)(lower_bound(U.begin(), U.end(), a) - U.begin());
}
inline bool Check(int i, int j)
{
        return ((ll)(X[i] - X[j]) * (X[i] - X[j]) + (ll)(Y[i] - Y[j]) * (Y[i] - Y[j]) <= (ll)(R[i] + R[j]) * (R[i] + R[j]));
}
inline void Get(int l, int r, int le, int ri, int i)
{
        l += (int)UX.size();
        r += (int)UX.size();
        for (; l < r; l >>= 1, r >>= 1)
        {
                if (l & 1)
                {
                        auto it = ST[l].lower_bound({le, -1});
                        while (it != ST[l].end() && it->first < ri)
                        {
                                if (M[it->second])
                                        it = ST[l].erase(it);
                                else if (Check(i, it->second))
                                        M[it->second] = i, it = ST[l].erase(it);
                                else
                                        it ++;
                        }
                        l ++;
                }
                if (r & 1)
                {
                        r --;
                        auto it = ST[r].lower_bound({le, -1});
                        while (it != ST[r].end() && it->first < ri)
                        {
                                if (M[it->second])
                                        it = ST[r].erase(it);
                                else if (Check(i, it->second))
                                        M[it->second] = i, it = ST[r].erase(it);
                                else
                                        it ++;
                        }
                }
        }
}
inline void Do(int i)
{
        M[i] = i;

        int lx = GetId(X[i] - R[i] * 2, UX);
        int rx = GetId(X[i] + R[i] * 2 + 1, UX);
        int ly = GetId(Y[i] - R[i] * 2, UY);
        int ry = GetId(Y[i] + R[i] * 2 + 1, UY);

        Get(lx, rx, ly, ry, i);
}
int main()
{
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
        {
                scanf("%d%d%d", &X[i], &Y[i], &R[i]);
                UX.push_back(X[i]);
                UY.push_back(Y[i]);
        }
        sort(UX.begin(), UX.end());
        UX.resize(unique(UX.begin(), UX.end()) - UX.begin());
        sort(UY.begin(), UY.end());
        UY.resize(unique(UY.begin(), UY.end()) - UY.begin());
        for (int i = 1; i <= n; i ++)
        {
                int x = GetId(X[i], UX);
                int y = GetId(Y[i], UY);
                V[x + (int)UX.size()].push_back({y, i});
        }
        for (int i = (int)UX.size(); i < (int)UX.size() * 2; i ++)
                sort(V[i].begin(), V[i].end());
        for (int i = (int)UX.size() - 1; i; i --)
                merge(V[i << 1].begin(), V[i << 1].end(), V[i << 1 ^ 1].begin(), V[i << 1 ^ 1].end(), back_inserter(V[i]));
        for (int i = 0; i < (int)UX.size() * 2; i ++)
                ST[i] = set < pair < int , int > > (V[i].begin(), V[i].end());
        set < pair < int , int > > TS;
        for (int i = 1; i <= n; i ++)
                TS.insert({-R[i], i});
        while (TS.size())
        {
                while (TS.size() && M[TS.begin()->second])
                        TS.erase(TS.begin());
                if (!TS.size())
                        break;
                int i = TS.begin()->second;
                TS.erase(TS.begin());
                Do(i);
        }
        for (int i = 1; i <= n; i ++)
                printf("%d ", M[i]);
        printf("\n");
        return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &n);
         ~~~~~^~~~~~~~~~
circle_selection.cpp:70:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d%d", &X[i], &Y[i], &R[i]);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1400 ms 395848 KB Output is correct
2 Correct 1374 ms 402080 KB Output is correct
3 Correct 1420 ms 402252 KB Output is correct
4 Incorrect 1442 ms 401892 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 42616 KB Output is correct
2 Correct 617 ms 154136 KB Output is correct
3 Correct 2095 ms 402880 KB Output is correct
4 Correct 2086 ms 402848 KB Output is correct
5 Correct 2107 ms 392788 KB Output is correct
6 Correct 943 ms 222472 KB Output is correct
7 Correct 450 ms 133096 KB Output is correct
8 Correct 92 ms 59124 KB Output is correct
9 Correct 2156 ms 403396 KB Output is correct
10 Correct 2140 ms 403784 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1826 ms 396528 KB Output is correct
2 Correct 1657 ms 406476 KB Output is correct
3 Correct 1562 ms 403564 KB Output is correct
4 Correct 1674 ms 402896 KB Output is correct
5 Correct 1738 ms 402764 KB Output is correct
6 Correct 1623 ms 404848 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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