oj.uz

Submission #260444

# Submission time Handle Problem Language Result Execution time Memory
260444 2020-08-10T09:18:03 Z Kastanda Circle selection (APIO18_circle_selection) C++11
100 / 100
 2555 ms 412480 KB 
// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005, INF = 1e9 + 9;
int n, X[N], Y[N], R[N], M[N];
vector < int > UX;
vector < pair < int , int > > V[N * 2];
set < pair < int , int > > ST[N * 2];
inline int GetId(int a)
{
        return (int)(lower_bound(UX.begin(), UX.end(), a) - UX.begin());
}
inline bool Check(int i, int j)
{
        return ((ll)(X[i] - X[j]) * (ll)(X[i] - X[j]) + (ll)(Y[i] - Y[j]) * (ll)(Y[i] - Y[j]) <= (ll)(R[i] + R[j]) * (ll)(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(max(X[i] - R[i] * 2LL, (ll)-INF));
        int rx = GetId(min(X[i] + R[i] * 2LL + 1, (ll)INF));
        int ly = max(Y[i] - R[i] * 2LL, (ll)-INF);
        int ry = min(Y[i] + R[i] * 2LL + 1, (ll)INF);

        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]);
        sort(UX.begin(), UX.end());
        UX.resize(unique(UX.begin(), UX.end()) - UX.begin());
        for (int i = 1; i <= n; i ++)
        {
                int x = GetId(X[i]);
                V[x + (int)UX.size()].push_back({Y[i], 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:69:53: 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]), UX.push_back(X[i]);
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42624 KB Output is correct
2 Correct 27 ms 42624 KB Output is correct
3 Correct 29 ms 42616 KB Output is correct
4 Correct 26 ms 42624 KB Output is correct
5 Correct 27 ms 42752 KB Output is correct
6 Correct 26 ms 42624 KB Output is correct
7 Correct 26 ms 42624 KB Output is correct
8 Correct 27 ms 42624 KB Output is correct
9 Correct 26 ms 42624 KB Output is correct
10 Correct 27 ms 42624 KB Output is correct
11 Correct 26 ms 42624 KB Output is correct
12 Correct 26 ms 42624 KB Output is correct
13 Correct 26 ms 42700 KB Output is correct
14 Correct 26 ms 42616 KB Output is correct
15 Correct 26 ms 42624 KB Output is correct
16 Correct 28 ms 43264 KB Output is correct
17 Correct 28 ms 43256 KB Output is correct
18 Correct 29 ms 43384 KB Output is correct
19 Correct 41 ms 46840 KB Output is correct
20 Correct 42 ms 46840 KB Output is correct
21 Correct 47 ms 46840 KB Output is correct
22 Correct 42 ms 46840 KB Output is correct
23 Correct 43 ms 46864 KB Output is correct
24 Correct 43 ms 46848 KB Output is correct
25 Correct 43 ms 46840 KB Output is correct
26 Correct 43 ms 46840 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 394684 KB Output is correct
2 Correct 1387 ms 394220 KB Output is correct
3 Correct 1502 ms 394472 KB Output is correct
4 Correct 1484 ms 393772 KB Output is correct
5 Correct 1369 ms 388064 KB Output is correct
6 Correct 1538 ms 407348 KB Output is correct
7 Correct 1583 ms 409712 KB Output is correct
8 Correct 1607 ms 409928 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 42624 KB Output is correct
2 Correct 593 ms 151096 KB Output is correct
3 Correct 1969 ms 393968 KB Output is correct
4 Correct 1961 ms 393884 KB Output is correct
5 Correct 2012 ms 383936 KB Output is correct
6 Correct 1018 ms 217872 KB Output is correct
7 Correct 433 ms 130924 KB Output is correct
8 Correct 110 ms 58868 KB Output is correct
9 Correct 2054 ms 394424 KB Output is correct
10 Correct 2037 ms 394340 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1694 ms 395440 KB Output is correct
2 Correct 1523 ms 398600 KB Output is correct
3 Correct 1617 ms 394208 KB Output is correct
4 Correct 1502 ms 394608 KB Output is correct
5 Correct 1596 ms 394300 KB Output is correct
6 Correct 1416 ms 395616 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42624 KB Output is correct
2 Correct 27 ms 42624 KB Output is correct
3 Correct 29 ms 42616 KB Output is correct
4 Correct 26 ms 42624 KB Output is correct
5 Correct 27 ms 42752 KB Output is correct
6 Correct 26 ms 42624 KB Output is correct
7 Correct 26 ms 42624 KB Output is correct
8 Correct 27 ms 42624 KB Output is correct
9 Correct 26 ms 42624 KB Output is correct
10 Correct 27 ms 42624 KB Output is correct
11 Correct 26 ms 42624 KB Output is correct
12 Correct 26 ms 42624 KB Output is correct
13 Correct 26 ms 42700 KB Output is correct
14 Correct 26 ms 42616 KB Output is correct
15 Correct 26 ms 42624 KB Output is correct
16 Correct 28 ms 43264 KB Output is correct
17 Correct 28 ms 43256 KB Output is correct
18 Correct 29 ms 43384 KB Output is correct
19 Correct 41 ms 46840 KB Output is correct
20 Correct 42 ms 46840 KB Output is correct
21 Correct 47 ms 46840 KB Output is correct
22 Correct 42 ms 46840 KB Output is correct
23 Correct 43 ms 46864 KB Output is correct
24 Correct 43 ms 46848 KB Output is correct
25 Correct 43 ms 46840 KB Output is correct
26 Correct 43 ms 46840 KB Output is correct
27 Correct 60 ms 51960 KB Output is correct
28 Correct 61 ms 51960 KB Output is correct
29 Correct 68 ms 51832 KB Output is correct
30 Correct 66 ms 51960 KB Output is correct
31 Correct 72 ms 51832 KB Output is correct
32 Correct 65 ms 51864 KB Output is correct
33 Correct 421 ms 151788 KB Output is correct
34 Correct 435 ms 151404 KB Output is correct
35 Correct 435 ms 151532 KB Output is correct
36 Correct 511 ms 151404 KB Output is correct
37 Correct 511 ms 153696 KB Output is correct
38 Correct 515 ms 153708 KB Output is correct
39 Correct 492 ms 110444 KB Output is correct
40 Correct 437 ms 110316 KB Output is correct
41 Correct 466 ms 110316 KB Output is correct
42 Correct 316 ms 112492 KB Output is correct
43 Correct 435 ms 153380 KB Output is correct
44 Correct 436 ms 153576 KB Output is correct
45 Correct 461 ms 153448 KB Output is correct
46 Correct 446 ms 153704 KB Output is correct
47 Correct 468 ms 153452 KB Output is correct
48 Correct 452 ms 153452 KB Output is correct
49 Correct 441 ms 153580 KB Output is correct
50 Correct 435 ms 153496 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42624 KB Output is correct
2 Correct 27 ms 42624 KB Output is correct
3 Correct 29 ms 42616 KB Output is correct
4 Correct 26 ms 42624 KB Output is correct
5 Correct 27 ms 42752 KB Output is correct
6 Correct 26 ms 42624 KB Output is correct
7 Correct 26 ms 42624 KB Output is correct
8 Correct 27 ms 42624 KB Output is correct
9 Correct 26 ms 42624 KB Output is correct
10 Correct 27 ms 42624 KB Output is correct
11 Correct 26 ms 42624 KB Output is correct
12 Correct 26 ms 42624 KB Output is correct
13 Correct 26 ms 42700 KB Output is correct
14 Correct 26 ms 42616 KB Output is correct
15 Correct 26 ms 42624 KB Output is correct
16 Correct 28 ms 43264 KB Output is correct
17 Correct 28 ms 43256 KB Output is correct
18 Correct 29 ms 43384 KB Output is correct
19 Correct 41 ms 46840 KB Output is correct
20 Correct 42 ms 46840 KB Output is correct
21 Correct 47 ms 46840 KB Output is correct
22 Correct 42 ms 46840 KB Output is correct
23 Correct 43 ms 46864 KB Output is correct
24 Correct 43 ms 46848 KB Output is correct
25 Correct 43 ms 46840 KB Output is correct
26 Correct 43 ms 46840 KB Output is correct
27 Correct 1408 ms 394684 KB Output is correct
28 Correct 1387 ms 394220 KB Output is correct
29 Correct 1502 ms 394472 KB Output is correct
30 Correct 1484 ms 393772 KB Output is correct
31 Correct 1369 ms 388064 KB Output is correct
32 Correct 1538 ms 407348 KB Output is correct
33 Correct 1583 ms 409712 KB Output is correct
34 Correct 1607 ms 409928 KB Output is correct
35 Correct 28 ms 42624 KB Output is correct
36 Correct 593 ms 151096 KB Output is correct
37 Correct 1969 ms 393968 KB Output is correct
38 Correct 1961 ms 393884 KB Output is correct
39 Correct 2012 ms 383936 KB Output is correct
40 Correct 1018 ms 217872 KB Output is correct
41 Correct 433 ms 130924 KB Output is correct
42 Correct 110 ms 58868 KB Output is correct
43 Correct 2054 ms 394424 KB Output is correct
44 Correct 2037 ms 394340 KB Output is correct
45 Correct 1694 ms 395440 KB Output is correct
46 Correct 1523 ms 398600 KB Output is correct
47 Correct 1617 ms 394208 KB Output is correct
48 Correct 1502 ms 394608 KB Output is correct
49 Correct 1596 ms 394300 KB Output is correct
50 Correct 1416 ms 395616 KB Output is correct
51 Correct 60 ms 51960 KB Output is correct
52 Correct 61 ms 51960 KB Output is correct
53 Correct 68 ms 51832 KB Output is correct
54 Correct 66 ms 51960 KB Output is correct
55 Correct 72 ms 51832 KB Output is correct
56 Correct 65 ms 51864 KB Output is correct
57 Correct 421 ms 151788 KB Output is correct
58 Correct 435 ms 151404 KB Output is correct
59 Correct 435 ms 151532 KB Output is correct
60 Correct 511 ms 151404 KB Output is correct
61 Correct 511 ms 153696 KB Output is correct
62 Correct 515 ms 153708 KB Output is correct
63 Correct 492 ms 110444 KB Output is correct
64 Correct 437 ms 110316 KB Output is correct
65 Correct 466 ms 110316 KB Output is correct
66 Correct 316 ms 112492 KB Output is correct
67 Correct 435 ms 153380 KB Output is correct
68 Correct 436 ms 153576 KB Output is correct
69 Correct 461 ms 153448 KB Output is correct
70 Correct 446 ms 153704 KB Output is correct
71 Correct 468 ms 153452 KB Output is correct
72 Correct 452 ms 153452 KB Output is correct
73 Correct 441 ms 153580 KB Output is correct
74 Correct 435 ms 153496 KB Output is correct
75 Correct 1462 ms 403360 KB Output is correct
76 Correct 1478 ms 403664 KB Output is correct
77 Correct 1556 ms 409312 KB Output is correct
78 Correct 1421 ms 403580 KB Output is correct
79 Correct 1521 ms 403044 KB Output is correct
80 Correct 1441 ms 403208 KB Output is correct
81 Correct 1905 ms 402656 KB Output is correct
82 Correct 1811 ms 401592 KB Output is correct
83 Correct 1813 ms 401920 KB Output is correct
84 Correct 1975 ms 404060 KB Output is correct
85 Correct 1911 ms 402016 KB Output is correct
86 Correct 1828 ms 401684 KB Output is correct
87 Correct 2555 ms 409440 KB Output is correct
88 Correct 1591 ms 256100 KB Output is correct
89 Correct 1603 ms 256096 KB Output is correct
90 Correct 1627 ms 256224 KB Output is correct
91 Correct 1607 ms 256124 KB Output is correct
92 Correct 1712 ms 255816 KB Output is correct
93 Correct 1522 ms 402532 KB Output is correct
94 Correct 1604 ms 179424 KB Output is correct
95 Correct 1567 ms 402400 KB Output is correct
96 Correct 1551 ms 404320 KB Output is correct
97 Correct 2170 ms 248288 KB Output is correct
98 Correct 1606 ms 410852 KB Output is correct
99 Correct 1741 ms 401408 KB Output is correct
100 Correct 1506 ms 400416 KB Output is correct
101 Correct 1629 ms 412480 KB Output is correct
102 Correct 1620 ms 403376 KB Output is correct
103 Correct 2364 ms 221892 KB Output is correct
104 Correct 1593 ms 400480 KB Output is correct
105 Correct 1035 ms 266640 KB Output is correct
106 Correct 1460 ms 402272 KB Output is correct
107 Correct 1462 ms 402280 KB Output is correct
108 Correct 1449 ms 402524 KB Output is correct
109 Correct 1501 ms 402784 KB Output is correct
110 Correct 1462 ms 402332 KB Output is correct
111 Correct 1473 ms 402384 KB Output is correct
112 Correct 1491 ms 402324 KB Output is correct
113 Correct 1481 ms 402220 KB Output is correct
114 Correct 1502 ms 402272 KB Output is correct
115 Correct 1483 ms 402056 KB Output is correct
116 Correct 1422 ms 401248 KB Output is correct