답안 #49662 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49662	2018-06-01T18:40:46 Z	gs14004	원 고르기 (APIO18_circle_selection)	C++17	100 / 100	2027 ms	464704 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 300005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;
typedef pair<int, int> pii;
 
int N;
int X[MAXN], Y[MAXN], R[MAXN], A[MAXN], P[MAXN], Q[MAXN];
int ans[MAXN];
 
int XX[MAXN*2], XC;
 
const int TS = 2097152, ST = TS/2-1;
struct NODE {
    vector <pii> arr;
    vector <int> nxt;
    int find(int n){ return nxt[n] == n ? n : (nxt[n] = find(nxt[n])); }
    void relax(){
        int n = sz(arr);
        nxt.resize(n+1);
        for (int i=0;i<=n;i++) nxt[i] = i;
    }
    void merge(const NODE &a, const NODE &b){
        int n = sz(a.arr), m = sz(b.arr);
        arr.resize(n+m);
        for (int i=0,j=0,k=0;i<n||j<m;){
            if (j == m || i < n && a.arr[i] < b.arr[j]) arr[k++] = a.arr[i++];
            else arr[k++] = b.arr[j++];
        }
        relax();
    }
} tree[TS];
 
inline bool intersect(int a, int b){ return (lld)(X[a]-X[b])*(X[a]-X[b]) + (lld)(Y[a]-Y[b])*(Y[a]-Y[b]) <= (lld)(R[a]+R[b])*(R[a]+R[b]); }
 
void doIt(int n)
{
    auto iterate = [&](NODE &v){
        for (int i=lower_bound(all(v.arr), pii(Y[n]-R[n], 0))-v.arr.begin();;i++){
            i = v.find(i);
            if (i >= sz(v.arr) || v.arr[i].first > Y[n]+R[n]) break;
            int t = v.arr[i].second;
            if (ans[t])
                v.nxt[i] = v.find(i+1);
            else if (intersect(n, t))
                ans[t] = n;
        }
    };
    for (int l=ST+P[n],r=ST+Q[n];l<=r;l>>=1,r>>=1){
        if (l&1) iterate(tree[l++]);
        if (!(r&1)) iterate(tree[r--]);
    }
}
 
int main()
{
    scanf("%d", &N);
    for (int i=1;i<=N;i++){
        scanf("%d%d%d", X+i, Y+i, R+i);
        A[i] = i;
        XX[++XC] = X[i]-R[i];
        XX[++XC] = X[i]+R[i];
    }
    sort(XX+1, XX+XC+1); XC = unique(XX+1, XX+XC+1)-XX-1;
    sort(A+1, A+N+1, [](const int &a, const int &b){
        return R[a] != R[b] ? R[a] > R[b] : a < b;
    });
 
    for (int i=1;i<=N;i++){
        P[i] = lower_bound(XX+1, XX+XC+1, X[i]-R[i]) - XX;
        Q[i] = lower_bound(XX+1, XX+XC+1, X[i]+R[i]) - XX;
        tree[ST+P[i]].arr.pb({Y[i]-R[i], i});
        tree[ST+P[i]].arr.pb({Y[i]+R[i], i});
        tree[ST+Q[i]].arr.pb({Y[i]-R[i], i});
        tree[ST+Q[i]].arr.pb({Y[i]+R[i], i});
    }
    for (int i=1;i<=XC;i++) sort(all(tree[ST+i].arr)), tree[ST+i].relax();
    for (int i=ST;i;i--) tree[i].merge(tree[i+i], tree[i+i+1]);
 
    for (int i=1;i<=N;i++) if (!ans[A[i]])
        doIt(A[i]);
         
    for (int i=1;i<=N;i++) printf("%d%s", ans[i], i < N ? " " : "");
    puts("");
}

Compilation message

circle_selection.cpp: In member function 'void NODE::merge(const NODE&, const NODE&)':
circle_selection.cpp:31:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if (j == m || i < n && a.arr[i] < b.arr[j]) arr[k++] = a.arr[i++];
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
circle_selection.cpp:63:14: 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
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	162 ms	131704 KB	Output is correct
2	Correct	165 ms	131812 KB	Output is correct
3	Correct	164 ms	131812 KB	Output is correct
4	Correct	165 ms	131836 KB	Output is correct
5	Correct	161 ms	131912 KB	Output is correct
6	Correct	165 ms	132044 KB	Output is correct
7	Correct	165 ms	132076 KB	Output is correct
8	Correct	180 ms	132136 KB	Output is correct
9	Correct	178 ms	132196 KB	Output is correct
10	Correct	163 ms	132196 KB	Output is correct
11	Correct	171 ms	132196 KB	Output is correct
12	Correct	170 ms	132196 KB	Output is correct
13	Correct	164 ms	132196 KB	Output is correct
14	Correct	164 ms	132196 KB	Output is correct
15	Correct	183 ms	132196 KB	Output is correct
16	Correct	174 ms	132988 KB	Output is correct
17	Correct	180 ms	133028 KB	Output is correct
18	Correct	173 ms	133216 KB	Output is correct
19	Correct	190 ms	137468 KB	Output is correct
20	Correct	264 ms	137468 KB	Output is correct
21	Correct	205 ms	137484 KB	Output is correct
22	Correct	213 ms	137640 KB	Output is correct
23	Correct	209 ms	137640 KB	Output is correct
24	Correct	190 ms	137640 KB	Output is correct
25	Correct	208 ms	137652 KB	Output is correct
26	Correct	180 ms	137652 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1771 ms	464500 KB	Output is correct
2	Correct	1651 ms	464576 KB	Output is correct
3	Correct	1646 ms	464576 KB	Output is correct
4	Correct	1712 ms	464704 KB	Output is correct
5	Correct	1418 ms	464704 KB	Output is correct
6	Correct	1587 ms	464704 KB	Output is correct
7	Correct	1502 ms	464704 KB	Output is correct
8	Correct	1383 ms	464704 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	161 ms	464704 KB	Output is correct
2	Correct	620 ms	464704 KB	Output is correct
3	Correct	1708 ms	464704 KB	Output is correct
4	Correct	1683 ms	464704 KB	Output is correct
5	Correct	1923 ms	464704 KB	Output is correct
6	Correct	982 ms	464704 KB	Output is correct
7	Correct	590 ms	464704 KB	Output is correct
8	Correct	244 ms	464704 KB	Output is correct
9	Correct	1927 ms	464704 KB	Output is correct
10	Correct	1840 ms	464704 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1695 ms	464704 KB	Output is correct
2	Correct	1458 ms	464704 KB	Output is correct
3	Correct	1624 ms	464704 KB	Output is correct
4	Correct	1587 ms	464704 KB	Output is correct
5	Correct	1564 ms	464704 KB	Output is correct
6	Correct	1749 ms	464704 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	162 ms	131704 KB	Output is correct
2	Correct	165 ms	131812 KB	Output is correct
3	Correct	164 ms	131812 KB	Output is correct
4	Correct	165 ms	131836 KB	Output is correct
5	Correct	161 ms	131912 KB	Output is correct
6	Correct	165 ms	132044 KB	Output is correct
7	Correct	165 ms	132076 KB	Output is correct
8	Correct	180 ms	132136 KB	Output is correct
9	Correct	178 ms	132196 KB	Output is correct
10	Correct	163 ms	132196 KB	Output is correct
11	Correct	171 ms	132196 KB	Output is correct
12	Correct	170 ms	132196 KB	Output is correct
13	Correct	164 ms	132196 KB	Output is correct
14	Correct	164 ms	132196 KB	Output is correct
15	Correct	183 ms	132196 KB	Output is correct
16	Correct	174 ms	132988 KB	Output is correct
17	Correct	180 ms	133028 KB	Output is correct
18	Correct	173 ms	133216 KB	Output is correct
19	Correct	190 ms	137468 KB	Output is correct
20	Correct	264 ms	137468 KB	Output is correct
21	Correct	205 ms	137484 KB	Output is correct
22	Correct	213 ms	137640 KB	Output is correct
23	Correct	209 ms	137640 KB	Output is correct
24	Correct	190 ms	137640 KB	Output is correct
25	Correct	208 ms	137652 KB	Output is correct
26	Correct	180 ms	137652 KB	Output is correct
27	Correct	216 ms	464704 KB	Output is correct
28	Correct	204 ms	464704 KB	Output is correct
29	Correct	205 ms	464704 KB	Output is correct
30	Correct	210 ms	464704 KB	Output is correct
31	Correct	201 ms	464704 KB	Output is correct
32	Correct	209 ms	464704 KB	Output is correct
33	Correct	614 ms	464704 KB	Output is correct
34	Correct	604 ms	464704 KB	Output is correct
35	Correct	566 ms	464704 KB	Output is correct
36	Correct	595 ms	464704 KB	Output is correct
37	Correct	630 ms	464704 KB	Output is correct
38	Correct	599 ms	464704 KB	Output is correct
39	Correct	433 ms	464704 KB	Output is correct
40	Correct	404 ms	464704 KB	Output is correct
41	Correct	406 ms	464704 KB	Output is correct
42	Correct	424 ms	464704 KB	Output is correct
43	Correct	513 ms	464704 KB	Output is correct
44	Correct	580 ms	464704 KB	Output is correct
45	Correct	583 ms	464704 KB	Output is correct
46	Correct	591 ms	464704 KB	Output is correct
47	Correct	706 ms	464704 KB	Output is correct
48	Correct	562 ms	464704 KB	Output is correct
49	Correct	563 ms	464704 KB	Output is correct
50	Correct	535 ms	464704 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	162 ms	131704 KB	Output is correct
2	Correct	165 ms	131812 KB	Output is correct
3	Correct	164 ms	131812 KB	Output is correct
4	Correct	165 ms	131836 KB	Output is correct
5	Correct	161 ms	131912 KB	Output is correct
6	Correct	165 ms	132044 KB	Output is correct
7	Correct	165 ms	132076 KB	Output is correct
8	Correct	180 ms	132136 KB	Output is correct
9	Correct	178 ms	132196 KB	Output is correct
10	Correct	163 ms	132196 KB	Output is correct
11	Correct	171 ms	132196 KB	Output is correct
12	Correct	170 ms	132196 KB	Output is correct
13	Correct	164 ms	132196 KB	Output is correct
14	Correct	164 ms	132196 KB	Output is correct
15	Correct	183 ms	132196 KB	Output is correct
16	Correct	174 ms	132988 KB	Output is correct
17	Correct	180 ms	133028 KB	Output is correct
18	Correct	173 ms	133216 KB	Output is correct
19	Correct	190 ms	137468 KB	Output is correct
20	Correct	264 ms	137468 KB	Output is correct
21	Correct	205 ms	137484 KB	Output is correct
22	Correct	213 ms	137640 KB	Output is correct
23	Correct	209 ms	137640 KB	Output is correct
24	Correct	190 ms	137640 KB	Output is correct
25	Correct	208 ms	137652 KB	Output is correct
26	Correct	180 ms	137652 KB	Output is correct
27	Correct	1771 ms	464500 KB	Output is correct
28	Correct	1651 ms	464576 KB	Output is correct
29	Correct	1646 ms	464576 KB	Output is correct
30	Correct	1712 ms	464704 KB	Output is correct
31	Correct	1418 ms	464704 KB	Output is correct
32	Correct	1587 ms	464704 KB	Output is correct
33	Correct	1502 ms	464704 KB	Output is correct
34	Correct	1383 ms	464704 KB	Output is correct
35	Correct	161 ms	464704 KB	Output is correct
36	Correct	620 ms	464704 KB	Output is correct
37	Correct	1708 ms	464704 KB	Output is correct
38	Correct	1683 ms	464704 KB	Output is correct
39	Correct	1923 ms	464704 KB	Output is correct
40	Correct	982 ms	464704 KB	Output is correct
41	Correct	590 ms	464704 KB	Output is correct
42	Correct	244 ms	464704 KB	Output is correct
43	Correct	1927 ms	464704 KB	Output is correct
44	Correct	1840 ms	464704 KB	Output is correct
45	Correct	1695 ms	464704 KB	Output is correct
46	Correct	1458 ms	464704 KB	Output is correct
47	Correct	1624 ms	464704 KB	Output is correct
48	Correct	1587 ms	464704 KB	Output is correct
49	Correct	1564 ms	464704 KB	Output is correct
50	Correct	1749 ms	464704 KB	Output is correct
51	Correct	216 ms	464704 KB	Output is correct
52	Correct	204 ms	464704 KB	Output is correct
53	Correct	205 ms	464704 KB	Output is correct
54	Correct	210 ms	464704 KB	Output is correct
55	Correct	201 ms	464704 KB	Output is correct
56	Correct	209 ms	464704 KB	Output is correct
57	Correct	614 ms	464704 KB	Output is correct
58	Correct	604 ms	464704 KB	Output is correct
59	Correct	566 ms	464704 KB	Output is correct
60	Correct	595 ms	464704 KB	Output is correct
61	Correct	630 ms	464704 KB	Output is correct
62	Correct	599 ms	464704 KB	Output is correct
63	Correct	433 ms	464704 KB	Output is correct
64	Correct	404 ms	464704 KB	Output is correct
65	Correct	406 ms	464704 KB	Output is correct
66	Correct	424 ms	464704 KB	Output is correct
67	Correct	513 ms	464704 KB	Output is correct
68	Correct	580 ms	464704 KB	Output is correct
69	Correct	583 ms	464704 KB	Output is correct
70	Correct	591 ms	464704 KB	Output is correct
71	Correct	706 ms	464704 KB	Output is correct
72	Correct	562 ms	464704 KB	Output is correct
73	Correct	563 ms	464704 KB	Output is correct
74	Correct	535 ms	464704 KB	Output is correct
75	Correct	1642 ms	464704 KB	Output is correct
76	Correct	1699 ms	464704 KB	Output is correct
77	Correct	1732 ms	464704 KB	Output is correct
78	Correct	1555 ms	464704 KB	Output is correct
79	Correct	1647 ms	464704 KB	Output is correct
80	Correct	1683 ms	464704 KB	Output is correct
81	Correct	1719 ms	464704 KB	Output is correct
82	Correct	1692 ms	464704 KB	Output is correct
83	Correct	1669 ms	464704 KB	Output is correct
84	Correct	1824 ms	464704 KB	Output is correct
85	Correct	1737 ms	464704 KB	Output is correct
86	Correct	1709 ms	464704 KB	Output is correct
87	Correct	2027 ms	464704 KB	Output is correct
88	Correct	975 ms	464704 KB	Output is correct
89	Correct	1117 ms	464704 KB	Output is correct
90	Correct	956 ms	464704 KB	Output is correct
91	Correct	986 ms	464704 KB	Output is correct
92	Correct	1024 ms	464704 KB	Output is correct
93	Correct	1517 ms	464704 KB	Output is correct
94	Correct	1473 ms	464704 KB	Output is correct
95	Correct	1431 ms	464704 KB	Output is correct
96	Correct	1511 ms	464704 KB	Output is correct
97	Correct	1266 ms	464704 KB	Output is correct
98	Correct	1514 ms	464704 KB	Output is correct
99	Correct	1616 ms	464704 KB	Output is correct
100	Correct	1678 ms	464704 KB	Output is correct
101	Correct	1639 ms	464704 KB	Output is correct
102	Correct	1656 ms	464704 KB	Output is correct
103	Correct	1738 ms	464704 KB	Output is correct
104	Correct	1651 ms	464704 KB	Output is correct
105	Correct	1045 ms	464704 KB	Output is correct
106	Correct	1514 ms	464704 KB	Output is correct
107	Correct	1473 ms	464704 KB	Output is correct
108	Correct	1534 ms	464704 KB	Output is correct
109	Correct	1482 ms	464704 KB	Output is correct
110	Correct	1489 ms	464704 KB	Output is correct
111	Correct	1524 ms	464704 KB	Output is correct
112	Correct	1568 ms	464704 KB	Output is correct
113	Correct	1590 ms	464704 KB	Output is correct
114	Correct	1606 ms	464704 KB	Output is correct
115	Correct	1433 ms	464704 KB	Output is correct
116	Correct	1520 ms	464704 KB	Output is correct

답안 #49662

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 13.0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
13.0 / 13.0