oj.uz

답안 #397454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397454 2021-05-02T09:27:14 Z parsabahrami 원 고르기 (APIO18_circle_selection) C++17
87 / 100
 3000 ms 337828 KB 
/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 3e5 + 4, MOD = 1e9 + 7;
int n, X[N], Y[N], R[N], ord[N], xord[N], pos[N], ret[N]; vector<int> ids;

int intersect(int i, int j) {
    ll x1 = X[i], x2 = X[j], y1 = Y[i], y2 = Y[j], r1 = R[i], r2 = R[j];
    return x1 * x1 + x2 * x2 + y1 * y1 + y2 * y2 - r1 * r1 - r2 * r2 <= 2 * (r1 * r2 + x1 * x2 + y1 * y2);
}

struct node : set<pii> {
    node *lc, *rc; 

    node() : lc(nullptr), rc(nullptr) {}

    void build(int l = 1, int r = n + 1) {
        for (int i = l; i < r; i++) {
            this->insert({Y[xord[i]], xord[i]});
        }
        if (r - l < 2) return;
        int md = (l + r) >> 1;
        lc = new node(), rc = new node();
        lc->build(l, md), rc->build(md, r);
    }

    void remove(int &p, int &id, int l = 1, int r = n + 1) {
        this->erase({Y[id], id});
        if (r - l < 2) return;
        int md = (l + r) >> 1;
        if (p < md) lc->remove(p, id, l, md);
        else rc->remove(p, id, md, r);
    }

    void get(ll xl, ll xr, ll yl, ll yr, int &id, node* &rt, int l = 1, int r = n + 1) {
        if (xr <= X[xord[l]] || X[xord[r - 1]] + 1 <= xl || this->empty()) return;
        if (xl <= X[xord[l]] && X[xord[r - 1]] + 1 <= xr) {
            for (auto it = this->lower_bound({yl, -1e9}); it != this->end() && it->F <= yr; ) {
                auto x = *it;
                if (ret[x.S]) this->erase(x);
                else if (intersect(id, x.S)) ret[x.S] = id;
                it = this->upper_bound(x);
            }
            return;
        }
        int md = (l + r) >> 1;
        lc->get(xl, xr, yl, yr, id, rt, l, md), rc->get(xl, xr, yl, yr, id, rt, md, r);
    }
    
};
node* seg;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d%d", &X[i], &Y[i], &R[i]);
    iota(ord + 1, ord + n + 1, 1);
    iota(xord + 1, xord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [&] (int i, int j) { return R[i] == R[j] ? i < j : R[i] > R[j]; });
    sort(xord + 1, xord + n + 1, [&] (int i, int j) { return X[i] < X[j]; });
    seg = new node(); seg->build();
    for (int i = 1; i <= n; i++) pos[xord[i]] = i;
    for (int _ = 1; _ <= n; _++) {
        int i = ord[_]; 
        if (ret[i]) continue;
        seg->get(X[i] - 2ll * R[i], X[i] + 2ll * R[i] + 1, Y[i] - 2ll * R[i], Y[i] + 2ll * R[i], i, seg);
    }
    for (int i = 1; i <= n; i++) printf("%d ", ret[i]);
    printf("\n");
    return 0;
}

Compilation message

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

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 3 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 1100 KB Output is correct
19 Correct 13 ms 4536 KB Output is correct
20 Correct 13 ms 4496 KB Output is correct
21 Correct 14 ms 4548 KB Output is correct
22 Correct 16 ms 4488 KB Output is correct
23 Correct 17 ms 4428 KB Output is correct
24 Correct 16 ms 4536 KB Output is correct
25 Correct 15 ms 4456 KB Output is correct
26 Correct 15 ms 4500 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1473 ms 335552 KB Output is correct
2 Correct 1427 ms 335468 KB Output is correct
3 Correct 1444 ms 335184 KB Output is correct
4 Correct 1367 ms 335572 KB Output is correct
5 Correct 1391 ms 333360 KB Output is correct
6 Correct 1607 ms 333500 KB Output is correct
7 Correct 1397 ms 333416 KB Output is correct
8 Correct 1439 ms 333480 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 640 ms 105076 KB Output is correct
3 Correct 2220 ms 336996 KB Output is correct
4 Correct 2300 ms 336880 KB Output is correct
5 Correct 2200 ms 327280 KB Output is correct
6 Correct 906 ms 168872 KB Output is correct
7 Correct 372 ms 85480 KB Output is correct
8 Correct 54 ms 15940 KB Output is correct
9 Correct 2273 ms 336912 KB Output is correct
10 Correct 2228 ms 337076 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2215 ms 336588 KB Output is correct
2 Correct 1872 ms 335956 KB Output is correct
3 Correct 1695 ms 336764 KB Output is correct
4 Correct 1979 ms 336132 KB Output is correct
5 Correct 2055 ms 336280 KB Output is correct
6 Correct 1839 ms 336516 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 3 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 1100 KB Output is correct
19 Correct 13 ms 4536 KB Output is correct
20 Correct 13 ms 4496 KB Output is correct
21 Correct 14 ms 4548 KB Output is correct
22 Correct 16 ms 4488 KB Output is correct
23 Correct 17 ms 4428 KB Output is correct
24 Correct 16 ms 4536 KB Output is correct
25 Correct 15 ms 4456 KB Output is correct
26 Correct 15 ms 4500 KB Output is correct
27 Correct 29 ms 9296 KB Output is correct
28 Correct 29 ms 9236 KB Output is correct
29 Correct 29 ms 9136 KB Output is correct
30 Correct 35 ms 9152 KB Output is correct
31 Correct 36 ms 9168 KB Output is correct
32 Correct 39 ms 9148 KB Output is correct
33 Correct 426 ms 105432 KB Output is correct
34 Correct 402 ms 105448 KB Output is correct
35 Correct 435 ms 105220 KB Output is correct
36 Correct 625 ms 104904 KB Output is correct
37 Correct 533 ms 105072 KB Output is correct
38 Correct 581 ms 104976 KB Output is correct
39 Correct 1290 ms 103504 KB Output is correct
40 Correct 1391 ms 103344 KB Output is correct
41 Correct 1327 ms 103508 KB Output is correct
42 Correct 491 ms 103752 KB Output is correct
43 Correct 427 ms 104900 KB Output is correct
44 Correct 397 ms 104904 KB Output is correct
45 Correct 406 ms 104932 KB Output is correct
46 Correct 450 ms 104980 KB Output is correct
47 Correct 409 ms 104908 KB Output is correct
48 Correct 447 ms 104904 KB Output is correct
49 Correct 448 ms 104924 KB Output is correct
50 Correct 405 ms 104996 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 3 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 1100 KB Output is correct
19 Correct 13 ms 4536 KB Output is correct
20 Correct 13 ms 4496 KB Output is correct
21 Correct 14 ms 4548 KB Output is correct
22 Correct 16 ms 4488 KB Output is correct
23 Correct 17 ms 4428 KB Output is correct
24 Correct 16 ms 4536 KB Output is correct
25 Correct 15 ms 4456 KB Output is correct
26 Correct 15 ms 4500 KB Output is correct
27 Correct 1473 ms 335552 KB Output is correct
28 Correct 1427 ms 335468 KB Output is correct
29 Correct 1444 ms 335184 KB Output is correct
30 Correct 1367 ms 335572 KB Output is correct
31 Correct 1391 ms 333360 KB Output is correct
32 Correct 1607 ms 333500 KB Output is correct
33 Correct 1397 ms 333416 KB Output is correct
34 Correct 1439 ms 333480 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 640 ms 105076 KB Output is correct
37 Correct 2220 ms 336996 KB Output is correct
38 Correct 2300 ms 336880 KB Output is correct
39 Correct 2200 ms 327280 KB Output is correct
40 Correct 906 ms 168872 KB Output is correct
41 Correct 372 ms 85480 KB Output is correct
42 Correct 54 ms 15940 KB Output is correct
43 Correct 2273 ms 336912 KB Output is correct
44 Correct 2228 ms 337076 KB Output is correct
45 Correct 2215 ms 336588 KB Output is correct
46 Correct 1872 ms 335956 KB Output is correct
47 Correct 1695 ms 336764 KB Output is correct
48 Correct 1979 ms 336132 KB Output is correct
49 Correct 2055 ms 336280 KB Output is correct
50 Correct 1839 ms 336516 KB Output is correct
51 Correct 29 ms 9296 KB Output is correct
52 Correct 29 ms 9236 KB Output is correct
53 Correct 29 ms 9136 KB Output is correct
54 Correct 35 ms 9152 KB Output is correct
55 Correct 36 ms 9168 KB Output is correct
56 Correct 39 ms 9148 KB Output is correct
57 Correct 426 ms 105432 KB Output is correct
58 Correct 402 ms 105448 KB Output is correct
59 Correct 435 ms 105220 KB Output is correct
60 Correct 625 ms 104904 KB Output is correct
61 Correct 533 ms 105072 KB Output is correct
62 Correct 581 ms 104976 KB Output is correct
63 Correct 1290 ms 103504 KB Output is correct
64 Correct 1391 ms 103344 KB Output is correct
65 Correct 1327 ms 103508 KB Output is correct
66 Correct 491 ms 103752 KB Output is correct
67 Correct 427 ms 104900 KB Output is correct
68 Correct 397 ms 104904 KB Output is correct
69 Correct 406 ms 104932 KB Output is correct
70 Correct 450 ms 104980 KB Output is correct
71 Correct 409 ms 104908 KB Output is correct
72 Correct 447 ms 104904 KB Output is correct
73 Correct 448 ms 104924 KB Output is correct
74 Correct 405 ms 104996 KB Output is correct
75 Correct 1734 ms 337828 KB Output is correct
76 Correct 1686 ms 337496 KB Output is correct
77 Correct 1462 ms 337716 KB Output is correct
78 Correct 1567 ms 337504 KB Output is correct
79 Correct 1784 ms 337348 KB Output is correct
80 Correct 1572 ms 337592 KB Output is correct
81 Correct 2438 ms 336708 KB Output is correct
82 Correct 2280 ms 336552 KB Output is correct
83 Correct 2312 ms 336500 KB Output is correct
84 Correct 2460 ms 337032 KB Output is correct
85 Correct 2268 ms 336588 KB Output is correct
86 Correct 2305 ms 336668 KB Output is correct
87 Execution timed out 3099 ms 334800 KB Time limit exceeded
88 Halted 0 ms 0 KB -