oj.uz

답안 #397546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397546 2021-05-02T10:52:59 Z AriaH 원 고르기 (APIO18_circle_selection) C++17
7 / 100
 3000 ms 247732 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 all(x) x.begin(), x.end()

#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 3e5 + 4, MOD = 1e9 + 7;
int n, X[N], Y[N], R[N], ord[N], ret[N], id[N]; ll base[N];
set<pii> seg[N << 1];

vector <ll> cm;

bool cmp(int i, int j) {
	if(R[i] == R[j]) return i < j;
    return R[i] > R[j];
}

int intersect(int i, int j) {
    return (base[i] + base[j] + 2ll * (1ll * X[i] * X[j] + 1ll * Y[i] * Y[j] + 1ll * R[i] * R[j])) >= 0;
}

int lwr(ll x) {
    return lower_bound(all(cm), x) - cm.begin();
}

void add(int pos, pii x) {
    pos += n;
    while (pos) {
	    seg[pos].insert(x);
	    pos >>= 1;
    }
}

void get(int ql, int qr, ll yl, ll yr, int p) {
    ql += n, qr += n + 1;
    while (qr - ql > 0) {
        if (ql & 1) {
            for (auto it = seg[ql].lower_bound({yl, -1e9}); it != seg[ql].end() && it->F <= yr; ) {
                auto x = *it;
                if (ret[x.S]) seg[ql].erase(x);
                else if (intersect(p, x.S)) ret[x.S] = p, seg[ql].erase(x);
                it = seg[ql].upper_bound(x);
            }
            ql++;
        } 
        if (qr & 1) {
            qr--;
            for (auto it = seg[qr].lower_bound({yl, -1e9}); it != seg[qr].end() && it->F <= yr; ) {
                auto x = *it;
                if (ret[x.S]) seg[qr].erase(x);
                else if (intersect(p, x.S)) ret[x.S] = p, seg[qr].erase(x);
                it = seg[qr].upper_bound(x);
            }
        }
        qr >>= 1, ql >>= 1;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d%d", &X[i], &Y[i], &R[i]), base[i] = 1ll * R[i] * R[i] - 1ll * X[i] * X[i] - 1ll * Y[i] * Y[i], cm.push_back(X[i]), ord[i] = i;
    sort(ord + 1, ord + n + 1, cmp);
    sort(all(cm));
    cm.resize(unique(all(cm)) - cm.begin());
    for(int i = 1; i <= n; i ++) {
	    int I = ord[i];
		///printf("i = %d I = %d X = %d\n", i, I, X[I]);
	    add(lwr(X[I]) + 1, make_pair(Y[I], I));
    }
    for (int _ = 1; _ <= n; _++) {
        int i = ord[_];
        if (ret[i]) continue;
        get(lwr(X[i] - 2ll * R[i]) + 1, lwr(X[i] + 2ll * R[i] + 1), Y[i] - 2ll * R[i], Y[i] + 2ll * R[i], i);
    }
    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:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         scanf("%d%d%d", &X[i], &Y[i], &R[i]), base[i] = 1ll * R[i] * R[i] - 1ll * X[i] * X[i] - 1ll * Y[i] * Y[i], cm.push_back(X[i]), ord[i] = i;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 16 ms 28512 KB Output is correct
3 Correct 16 ms 28520 KB Output is correct
4 Correct 16 ms 28492 KB Output is correct
5 Correct 16 ms 28472 KB Output is correct
6 Correct 16 ms 28552 KB Output is correct
7 Correct 16 ms 28492 KB Output is correct
8 Correct 17 ms 28492 KB Output is correct
9 Correct 16 ms 28492 KB Output is correct
10 Correct 16 ms 28444 KB Output is correct
11 Correct 16 ms 28492 KB Output is correct
12 Correct 16 ms 28548 KB Output is correct
13 Correct 16 ms 28492 KB Output is correct
14 Correct 16 ms 28492 KB Output is correct
15 Correct 16 ms 28524 KB Output is correct
16 Correct 18 ms 29056 KB Output is correct
17 Correct 18 ms 29032 KB Output is correct
18 Correct 18 ms 29004 KB Output is correct
19 Correct 34 ms 31844 KB Output is correct
20 Correct 33 ms 31852 KB Output is correct
21 Correct 36 ms 31836 KB Output is correct
22 Correct 39 ms 31820 KB Output is correct
23 Correct 36 ms 31748 KB Output is correct
24 Correct 35 ms 31852 KB Output is correct
25 Correct 34 ms 31828 KB Output is correct
26 Correct 35 ms 31824 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3106 ms 244392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28476 KB Output is correct
2 Correct 1426 ms 115828 KB Output is correct
3 Execution timed out 3069 ms 245544 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3097 ms 247732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 16 ms 28512 KB Output is correct
3 Correct 16 ms 28520 KB Output is correct
4 Correct 16 ms 28492 KB Output is correct
5 Correct 16 ms 28472 KB Output is correct
6 Correct 16 ms 28552 KB Output is correct
7 Correct 16 ms 28492 KB Output is correct
8 Correct 17 ms 28492 KB Output is correct
9 Correct 16 ms 28492 KB Output is correct
10 Correct 16 ms 28444 KB Output is correct
11 Correct 16 ms 28492 KB Output is correct
12 Correct 16 ms 28548 KB Output is correct
13 Correct 16 ms 28492 KB Output is correct
14 Correct 16 ms 28492 KB Output is correct
15 Correct 16 ms 28524 KB Output is correct
16 Correct 18 ms 29056 KB Output is correct
17 Correct 18 ms 29032 KB Output is correct
18 Correct 18 ms 29004 KB Output is correct
19 Correct 34 ms 31844 KB Output is correct
20 Correct 33 ms 31852 KB Output is correct
21 Correct 36 ms 31836 KB Output is correct
22 Correct 39 ms 31820 KB Output is correct
23 Correct 36 ms 31748 KB Output is correct
24 Correct 35 ms 31852 KB Output is correct
25 Correct 34 ms 31828 KB Output is correct
26 Correct 35 ms 31824 KB Output is correct
27 Correct 69 ms 35572 KB Output is correct
28 Correct 61 ms 35584 KB Output is correct
29 Correct 69 ms 35564 KB Output is correct
30 Correct 63 ms 35652 KB Output is correct
31 Correct 62 ms 35656 KB Output is correct
32 Correct 64 ms 35652 KB Output is correct
33 Correct 1318 ms 115692 KB Output is correct
34 Correct 1351 ms 115668 KB Output is correct
35 Correct 1438 ms 115720 KB Output is correct
36 Correct 1457 ms 115604 KB Output is correct
37 Correct 1429 ms 115696 KB Output is correct
38 Correct 1556 ms 115712 KB Output is correct
39 Correct 2963 ms 112312 KB Output is correct
40 Correct 2809 ms 112404 KB Output is correct
41 Execution timed out 3047 ms 112392 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 16 ms 28512 KB Output is correct
3 Correct 16 ms 28520 KB Output is correct
4 Correct 16 ms 28492 KB Output is correct
5 Correct 16 ms 28472 KB Output is correct
6 Correct 16 ms 28552 KB Output is correct
7 Correct 16 ms 28492 KB Output is correct
8 Correct 17 ms 28492 KB Output is correct
9 Correct 16 ms 28492 KB Output is correct
10 Correct 16 ms 28444 KB Output is correct
11 Correct 16 ms 28492 KB Output is correct
12 Correct 16 ms 28548 KB Output is correct
13 Correct 16 ms 28492 KB Output is correct
14 Correct 16 ms 28492 KB Output is correct
15 Correct 16 ms 28524 KB Output is correct
16 Correct 18 ms 29056 KB Output is correct
17 Correct 18 ms 29032 KB Output is correct
18 Correct 18 ms 29004 KB Output is correct
19 Correct 34 ms 31844 KB Output is correct
20 Correct 33 ms 31852 KB Output is correct
21 Correct 36 ms 31836 KB Output is correct
22 Correct 39 ms 31820 KB Output is correct
23 Correct 36 ms 31748 KB Output is correct
24 Correct 35 ms 31852 KB Output is correct
25 Correct 34 ms 31828 KB Output is correct
26 Correct 35 ms 31824 KB Output is correct
27 Execution timed out 3106 ms 244392 KB Time limit exceeded
28 Halted 0 ms 0 KB -