oj.uz

Submission #397547

# Submission time Handle Problem Language Result Execution time Memory
397547 2021-05-02T10:53:17 Z parsabahrami Circle selection (APIO18_circle_selection) C++17
37 / 100
 3000 ms 240084 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; ) {
                if (ret[it->S]) it = seg[ql].erase(it);
                else if (intersect(p, it->S)) ret[it->S] = p, it = seg[ql].erase(it);
                else it++;
            }
            ql++;
        } 
        if (qr & 1) {
            qr--;
            for (auto it = seg[qr].lower_bound({yl, -1e9}); it != seg[qr].end() && it->F <= yr; ) {
                if (ret[it->S]) it = seg[qr].erase(it);
                else if (intersect(p, it->S)) ret[it->S] = p, it = seg[qr].erase(it);
                else it++;
            }
        }
        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];
	    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:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 15 ms 28476 KB Output is correct
5 Correct 15 ms 28472 KB Output is correct
6 Correct 15 ms 28444 KB Output is correct
7 Correct 15 ms 28560 KB Output is correct
8 Correct 16 ms 28460 KB Output is correct
9 Correct 18 ms 28552 KB Output is correct
10 Correct 18 ms 28492 KB Output is correct
11 Correct 36 ms 28492 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 18 ms 28556 KB Output is correct
14 Correct 19 ms 28536 KB Output is correct
15 Correct 20 ms 28520 KB Output is correct
16 Correct 22 ms 28996 KB Output is correct
17 Correct 22 ms 29044 KB Output is correct
18 Correct 19 ms 29032 KB Output is correct
19 Correct 34 ms 31752 KB Output is correct
20 Correct 33 ms 31812 KB Output is correct
21 Correct 33 ms 31732 KB Output is correct
22 Correct 35 ms 31828 KB Output is correct
23 Correct 37 ms 31716 KB Output is correct
24 Correct 37 ms 31820 KB Output is correct
25 Correct 37 ms 31812 KB Output is correct
26 Correct 39 ms 31820 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3099 ms 228152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 1565 ms 115756 KB Output is correct
3 Execution timed out 3065 ms 240084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3107 ms 230884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 15 ms 28476 KB Output is correct
5 Correct 15 ms 28472 KB Output is correct
6 Correct 15 ms 28444 KB Output is correct
7 Correct 15 ms 28560 KB Output is correct
8 Correct 16 ms 28460 KB Output is correct
9 Correct 18 ms 28552 KB Output is correct
10 Correct 18 ms 28492 KB Output is correct
11 Correct 36 ms 28492 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 18 ms 28556 KB Output is correct
14 Correct 19 ms 28536 KB Output is correct
15 Correct 20 ms 28520 KB Output is correct
16 Correct 22 ms 28996 KB Output is correct
17 Correct 22 ms 29044 KB Output is correct
18 Correct 19 ms 29032 KB Output is correct
19 Correct 34 ms 31752 KB Output is correct
20 Correct 33 ms 31812 KB Output is correct
21 Correct 33 ms 31732 KB Output is correct
22 Correct 35 ms 31828 KB Output is correct
23 Correct 37 ms 31716 KB Output is correct
24 Correct 37 ms 31820 KB Output is correct
25 Correct 37 ms 31812 KB Output is correct
26 Correct 39 ms 31820 KB Output is correct
27 Correct 61 ms 35824 KB Output is correct
28 Correct 68 ms 35656 KB Output is correct
29 Correct 60 ms 35544 KB Output is correct
30 Correct 66 ms 35660 KB Output is correct
31 Correct 61 ms 35620 KB Output is correct
32 Correct 62 ms 35624 KB Output is correct
33 Correct 1315 ms 115596 KB Output is correct
34 Correct 1275 ms 115776 KB Output is correct
35 Correct 1301 ms 115768 KB Output is correct
36 Correct 1363 ms 115696 KB Output is correct
37 Correct 1351 ms 115640 KB Output is correct
38 Correct 1372 ms 115672 KB Output is correct
39 Correct 2331 ms 112380 KB Output is correct
40 Correct 2354 ms 112392 KB Output is correct
41 Correct 2368 ms 112572 KB Output is correct
42 Correct 1308 ms 112488 KB Output is correct
43 Correct 893 ms 115684 KB Output is correct
44 Correct 893 ms 115656 KB Output is correct
45 Correct 912 ms 115616 KB Output is correct
46 Correct 893 ms 115596 KB Output is correct
47 Correct 893 ms 115640 KB Output is correct
48 Correct 900 ms 115640 KB Output is correct
49 Correct 901 ms 115760 KB Output is correct
50 Correct 904 ms 115728 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 15 ms 28476 KB Output is correct
5 Correct 15 ms 28472 KB Output is correct
6 Correct 15 ms 28444 KB Output is correct
7 Correct 15 ms 28560 KB Output is correct
8 Correct 16 ms 28460 KB Output is correct
9 Correct 18 ms 28552 KB Output is correct
10 Correct 18 ms 28492 KB Output is correct
11 Correct 36 ms 28492 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 18 ms 28556 KB Output is correct
14 Correct 19 ms 28536 KB Output is correct
15 Correct 20 ms 28520 KB Output is correct
16 Correct 22 ms 28996 KB Output is correct
17 Correct 22 ms 29044 KB Output is correct
18 Correct 19 ms 29032 KB Output is correct
19 Correct 34 ms 31752 KB Output is correct
20 Correct 33 ms 31812 KB Output is correct
21 Correct 33 ms 31732 KB Output is correct
22 Correct 35 ms 31828 KB Output is correct
23 Correct 37 ms 31716 KB Output is correct
24 Correct 37 ms 31820 KB Output is correct
25 Correct 37 ms 31812 KB Output is correct
26 Correct 39 ms 31820 KB Output is correct
27 Execution timed out 3099 ms 228152 KB Time limit exceeded
28 Halted 0 ms 0 KB -