oj.uz

Submission #397470

# Submission time Handle Problem Language Result Execution time Memory
397470 2021-05-02T09:35:49 Z AriaH Circle selection (APIO18_circle_selection) C++11
87 / 100
 3000 ms 333204 KB 
/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
 
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;

ll base[N];

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;
}
 
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]);
    for(int i = 1 ;i <= n; i ++)
    {
	base[i] = 1ll * R[i] * R[i] - 1ll * X[i] * X[i] - 1ll * Y[i] * Y[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:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         scanf("%d%d%d", &X[i], &Y[i], &R[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 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 336 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 332 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 332 KB Output is correct
16 Correct 3 ms 1004 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 13 ms 4560 KB Output is correct
20 Correct 13 ms 4556 KB Output is correct
21 Correct 14 ms 4556 KB Output is correct
22 Correct 15 ms 4580 KB Output is correct
23 Correct 17 ms 4496 KB Output is correct
24 Correct 15 ms 4580 KB Output is correct
25 Correct 15 ms 4556 KB Output is correct
26 Correct 15 ms 4568 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1483 ms 332276 KB Output is correct
2 Correct 1517 ms 332744 KB Output is correct
3 Correct 1416 ms 332444 KB Output is correct
4 Correct 1399 ms 333204 KB Output is correct
5 Correct 1522 ms 332972 KB Output is correct
6 Correct 1587 ms 333100 KB Output is correct
7 Correct 1444 ms 332816 KB Output is correct
8 Correct 1462 ms 331604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 617 ms 103340 KB Output is correct
3 Correct 2269 ms 331248 KB Output is correct
4 Correct 2269 ms 332092 KB Output is correct
5 Correct 2166 ms 322364 KB Output is correct
6 Correct 889 ms 166664 KB Output is correct
7 Correct 390 ms 84712 KB Output is correct
8 Correct 58 ms 15812 KB Output is correct
9 Correct 2236 ms 331988 KB Output is correct
10 Correct 2213 ms 332144 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2087 ms 331840 KB Output is correct
2 Correct 1794 ms 331916 KB Output is correct
3 Correct 1684 ms 331516 KB Output is correct
4 Correct 1917 ms 331864 KB Output is correct
5 Correct 1878 ms 331752 KB Output is correct
6 Correct 1676 ms 331140 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 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 336 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 332 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 332 KB Output is correct
16 Correct 3 ms 1004 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 13 ms 4560 KB Output is correct
20 Correct 13 ms 4556 KB Output is correct
21 Correct 14 ms 4556 KB Output is correct
22 Correct 15 ms 4580 KB Output is correct
23 Correct 17 ms 4496 KB Output is correct
24 Correct 15 ms 4580 KB Output is correct
25 Correct 15 ms 4556 KB Output is correct
26 Correct 15 ms 4568 KB Output is correct
27 Correct 29 ms 9304 KB Output is correct
28 Correct 30 ms 9284 KB Output is correct
29 Correct 28 ms 9244 KB Output is correct
30 Correct 35 ms 9268 KB Output is correct
31 Correct 33 ms 9260 KB Output is correct
32 Correct 33 ms 9280 KB Output is correct
33 Correct 384 ms 103788 KB Output is correct
34 Correct 387 ms 103664 KB Output is correct
35 Correct 419 ms 103748 KB Output is correct
36 Correct 536 ms 103660 KB Output is correct
37 Correct 532 ms 103652 KB Output is correct
38 Correct 552 ms 103620 KB Output is correct
39 Correct 1285 ms 103764 KB Output is correct
40 Correct 1290 ms 103712 KB Output is correct
41 Correct 1311 ms 103592 KB Output is correct
42 Correct 480 ms 103424 KB Output is correct
43 Correct 396 ms 103592 KB Output is correct
44 Correct 400 ms 103592 KB Output is correct
45 Correct 396 ms 103592 KB Output is correct
46 Correct 399 ms 103596 KB Output is correct
47 Correct 396 ms 103604 KB Output is correct
48 Correct 394 ms 103592 KB Output is correct
49 Correct 400 ms 103548 KB Output is correct
50 Correct 390 ms 103556 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 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 336 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 332 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 332 KB Output is correct
16 Correct 3 ms 1004 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 13 ms 4560 KB Output is correct
20 Correct 13 ms 4556 KB Output is correct
21 Correct 14 ms 4556 KB Output is correct
22 Correct 15 ms 4580 KB Output is correct
23 Correct 17 ms 4496 KB Output is correct
24 Correct 15 ms 4580 KB Output is correct
25 Correct 15 ms 4556 KB Output is correct
26 Correct 15 ms 4568 KB Output is correct
27 Correct 1483 ms 332276 KB Output is correct
28 Correct 1517 ms 332744 KB Output is correct
29 Correct 1416 ms 332444 KB Output is correct
30 Correct 1399 ms 333204 KB Output is correct
31 Correct 1522 ms 332972 KB Output is correct
32 Correct 1587 ms 333100 KB Output is correct
33 Correct 1444 ms 332816 KB Output is correct
34 Correct 1462 ms 331604 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 617 ms 103340 KB Output is correct
37 Correct 2269 ms 331248 KB Output is correct
38 Correct 2269 ms 332092 KB Output is correct
39 Correct 2166 ms 322364 KB Output is correct
40 Correct 889 ms 166664 KB Output is correct
41 Correct 390 ms 84712 KB Output is correct
42 Correct 58 ms 15812 KB Output is correct
43 Correct 2236 ms 331988 KB Output is correct
44 Correct 2213 ms 332144 KB Output is correct
45 Correct 2087 ms 331840 KB Output is correct
46 Correct 1794 ms 331916 KB Output is correct
47 Correct 1684 ms 331516 KB Output is correct
48 Correct 1917 ms 331864 KB Output is correct
49 Correct 1878 ms 331752 KB Output is correct
50 Correct 1676 ms 331140 KB Output is correct
51 Correct 29 ms 9304 KB Output is correct
52 Correct 30 ms 9284 KB Output is correct
53 Correct 28 ms 9244 KB Output is correct
54 Correct 35 ms 9268 KB Output is correct
55 Correct 33 ms 9260 KB Output is correct
56 Correct 33 ms 9280 KB Output is correct
57 Correct 384 ms 103788 KB Output is correct
58 Correct 387 ms 103664 KB Output is correct
59 Correct 419 ms 103748 KB Output is correct
60 Correct 536 ms 103660 KB Output is correct
61 Correct 532 ms 103652 KB Output is correct
62 Correct 552 ms 103620 KB Output is correct
63 Correct 1285 ms 103764 KB Output is correct
64 Correct 1290 ms 103712 KB Output is correct
65 Correct 1311 ms 103592 KB Output is correct
66 Correct 480 ms 103424 KB Output is correct
67 Correct 396 ms 103592 KB Output is correct
68 Correct 400 ms 103592 KB Output is correct
69 Correct 396 ms 103592 KB Output is correct
70 Correct 399 ms 103596 KB Output is correct
71 Correct 396 ms 103604 KB Output is correct
72 Correct 394 ms 103592 KB Output is correct
73 Correct 400 ms 103548 KB Output is correct
74 Correct 390 ms 103556 KB Output is correct
75 Correct 1564 ms 331556 KB Output is correct
76 Correct 1500 ms 331916 KB Output is correct
77 Correct 1583 ms 331892 KB Output is correct
78 Correct 1519 ms 331592 KB Output is correct
79 Correct 1723 ms 331844 KB Output is correct
80 Correct 1579 ms 331640 KB Output is correct
81 Correct 2307 ms 331764 KB Output is correct
82 Correct 2181 ms 332176 KB Output is correct
83 Correct 2237 ms 331760 KB Output is correct
84 Correct 2419 ms 331464 KB Output is correct
85 Correct 2174 ms 331360 KB Output is correct
86 Correct 2127 ms 331448 KB Output is correct
87 Execution timed out 3076 ms 329240 KB Time limit exceeded
88 Halted 0 ms 0 KB -