oj.uz

Submission #499282

# Submission time Handle Problem Language Result Execution time Memory
499282 2021-12-27T18:45:11 Z _martynas Circle selection (APIO18_circle_selection) C++11
87 / 100
 3000 ms 722352 KB 
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

using ll = long long;

const ll MOD = 1e9+7;

const int MAX_N = 3e5+5;

int n;
struct Node
{
    ll x, y, r;
    int p;
    bool visited;
} A[MAX_N];

struct LLNode
{
    int idx;
    LLNode* next = nullptr;

    inline LLNode()
    {
    }

    inline LLNode(const int & val)
        : idx(val)
    {
    }
} LLNodes[MAX_N];
int llcounter = 0;

inline LLNode* getLLNode()
{
    return &LLNodes[llcounter++];
}

int dup;

struct Quad;
inline Quad* getQuadNode();

struct Quad
{
    ll l, r, bot, top;
    array<Quad*, 4> childs = {};
    LLNode* llnode = nullptr;
    int sz;

    inline Quad()
    {
    }

    inline Quad(const ll & _l, const ll & _r, const ll & _bot, const ll & _top)
        : l(_l), r(_r), bot(_bot), top(_top)
    {
        sz = 0;
    }

    void add(const ll & x, const ll & y, const int & idx)
    {
        if(x < l || x > r || y < bot || y > top) {
            return;
        }

        sz++;
//        cerr << "l = " << l << ", r = " << r << ", "
//             << "bot = " << bot << ", top = " << top << "\n";
        if(l == r && bot == top) {
            if(llnode == nullptr) {
                llnode = getLLNode();
                llnode->idx = idx;
            }
            else {
                //dup++;
                LLNode* temp = getLLNode();
                temp->idx = idx;
                temp->next = llnode;
                llnode = temp;
            }
        }
        else {
            ll midH, midV;
            midH = l+(r-l)/2;
            midV = bot+(top-bot)/2;

            if(l != r && top != bot) {
                if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > midV)) {
                    childs[0] = getQuadNode();
                    childs[0]->l = l;
                    childs[0]->r = midH;
                    childs[0]->bot = bot;
                    childs[0]->top = midV;
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > midV)) {
                    childs[1] = getQuadNode();
                    childs[1]->l = midH+1;
                    childs[1]->r = r;
                    childs[1]->bot = bot;
                    childs[1]->top = midV;
                }
                else if(childs[2] == nullptr && !(x < l || x > midH || y < midV+1 || y > top)) {
                    childs[2] = getQuadNode();
                    childs[2]->l = l;
                    childs[2]->r = midH;
                    childs[2]->bot = midV+1;
                    childs[2]->top = top;
                }
                else if(childs[3] == nullptr && !(x < midH+1 || x > r || y < midV+1 || y > top)) {
                    childs[3] = getQuadNode();
                    childs[3]->l = midH+1;
                    childs[3]->r = r;
                    childs[3]->bot = midV+1;
                    childs[3]->top = top;
                }
            }
            else if(l != r) {
                if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > top)) {
                    childs[0] = getQuadNode();
                    childs[0]->l = l;
                    childs[0]->r = midH;
                    childs[0]->bot = bot;
                    childs[0]->top = top;
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > top)) {
                    childs[1] = getQuadNode();
                    childs[1]->l = midH+1;
                    childs[1]->r = r;
                    childs[1]->bot = bot;
                    childs[1]->top = top;
                }
            }
            else if(top != bot) {
                if(childs[0] == nullptr && !(x < l || x > r || y < bot || y > midV)) {
                    childs[0] = getQuadNode();
                    childs[0]->l = l;
                    childs[0]->r = r;
                    childs[0]->bot = bot;
                    childs[0]->top = midV;
                }
                else if(childs[1] == nullptr && !(x < l || x > r || y < midV+1 || y > top)) {
                    childs[1] = getQuadNode();
                    childs[1]->l = l;
                    childs[1]->r = r;
                    childs[1]->bot = midV+1;
                    childs[1]->top = top;
                }
            }

            for(int k = 0; k < 4; k++) {
                if(childs[k] != nullptr) {
                    childs[k]->add(x, y, idx);
                }
            }
        }
    }

    void setInRange(const ll & x, const ll & y, const ll & radius, const int & idx)
    {
        if(x+2*radius < l || x-2*radius > r || y+2*radius < bot || y-2*radius > top || sz == 0) {
            return;
        }
//        cerr << "l = " << l << ", r = " << r << ", "
//             << "bot = " << bot << ", top = " << top << "\n";
        if(l == r && bot == top) {
            while(llnode != nullptr &&
                (A[idx].r+A[llnode->idx].r)*(A[idx].r+A[llnode->idx].r)
                >= llabs(A[idx].x-A[llnode->idx].x)*llabs(A[idx].x-A[llnode->idx].x)
                +llabs(A[idx].y-A[llnode->idx].y)*llabs(A[idx].y-A[llnode->idx].y)) {
                A[llnode->idx].p = idx;
                A[llnode->idx].visited = true;
                sz--;
                llnode = llnode->next;
            }
            return;
        }

        int cnt = 0;
        for(int k = 0; k < 4; k++) {
            if(childs[k] != nullptr) {
                childs[k]->setInRange(x, y, radius, idx);
                cnt += childs[k]->sz;
            }
        }
        sz = cnt;
    }
} QuadNodes[MAX_N*30];
int quadcounter = 0;
inline Quad* getQuadNode()
{
    return &QuadNodes[quadcounter++];
}

Quad Q(-1000000000, 1000000000, -1000000000, 1000000000);

inline int nextInt()
{
	int c = getchar();
	while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
	}
	int x = 0;
	bool neg = false;
	if (c == '-') {
		neg = true;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x*10+(c-'0');
		c = getchar();
	}
	if (neg)
		return -x;
	return x;
}

int main()
{
    //auto stop = steady_clock::now();

    n = nextInt();
    for(int i = 0; i < n; i++) {
        A[i].x = nextInt();
        A[i].y = nextInt();
        A[i].r = nextInt();
    }

    //cerr << "Exec: " << duration_cast<milliseconds>(steady_clock::now()-stop).count() << " ms\n";

    vector<int> I(n);
    iota(I.begin(), I.end(), 0);
    sort(I.begin(), I.end(),
    [&](int a, int b)
    {
        return A[a].r > A[b].r || (A[a].r == A[b].r && a < b);
    });

    for(int i = n-1; i >= 0; i--) {
        int idx = I[i];
        //cerr << i << " started\n";
        Q.add(A[idx].x, A[idx].y, idx);
        //cerr << i << " finished\n";
    }

    for(int i = 0; i < n; i++) {
        int idx = I[i];
        if(A[idx].visited) continue;
        Q.setInRange(A[idx].x, A[idx].y, A[idx].r, idx);
    }

    for(int i = 0; i < n; i++) {
        cout << 1+A[i].p << " ";
    }
    cout << "\n";

//    cerr << "Dupe: " << dup << "\n";
//    cerr << "Exec: " << duration_cast<milliseconds>(steady_clock::now()-stop).count() << " ms\n";

    return 0;
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 709584 KB Output is correct
2 Correct 252 ms 709420 KB Output is correct
3 Correct 248 ms 709444 KB Output is correct
4 Correct 249 ms 709608 KB Output is correct
5 Correct 254 ms 709484 KB Output is correct
6 Correct 249 ms 709476 KB Output is correct
7 Correct 279 ms 709396 KB Output is correct
8 Correct 246 ms 709464 KB Output is correct
9 Correct 249 ms 709448 KB Output is correct
10 Correct 257 ms 709440 KB Output is correct
11 Correct 247 ms 709492 KB Output is correct
12 Correct 266 ms 709476 KB Output is correct
13 Correct 254 ms 709384 KB Output is correct
14 Correct 257 ms 709420 KB Output is correct
15 Correct 251 ms 709428 KB Output is correct
16 Correct 245 ms 709500 KB Output is correct
17 Correct 263 ms 709420 KB Output is correct
18 Correct 253 ms 709560 KB Output is correct
19 Correct 266 ms 709640 KB Output is correct
20 Correct 255 ms 709572 KB Output is correct
21 Correct 266 ms 709676 KB Output is correct
22 Correct 273 ms 709604 KB Output is correct
23 Correct 251 ms 709588 KB Output is correct
24 Correct 294 ms 709696 KB Output is correct
25 Correct 254 ms 709604 KB Output is correct
26 Correct 272 ms 709608 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 722248 KB Output is correct
2 Correct 970 ms 722116 KB Output is correct
3 Correct 1004 ms 721832 KB Output is correct
4 Correct 958 ms 722112 KB Output is correct
5 Correct 726 ms 721844 KB Output is correct
6 Correct 940 ms 721956 KB Output is correct
7 Correct 799 ms 722136 KB Output is correct
8 Correct 875 ms 721916 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 709468 KB Output is correct
2 Correct 594 ms 713792 KB Output is correct
3 Correct 1442 ms 722124 KB Output is correct
4 Correct 1442 ms 722124 KB Output is correct
5 Correct 1394 ms 721840 KB Output is correct
6 Correct 765 ms 716132 KB Output is correct
7 Correct 482 ms 712900 KB Output is correct
8 Correct 287 ms 710300 KB Output is correct
9 Correct 1466 ms 722120 KB Output is correct
10 Correct 1320 ms 722124 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 721976 KB Output is correct
2 Correct 1271 ms 722120 KB Output is correct
3 Correct 1161 ms 721736 KB Output is correct
4 Correct 1300 ms 722116 KB Output is correct
5 Correct 1280 ms 722172 KB Output is correct
6 Correct 1079 ms 721476 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 709584 KB Output is correct
2 Correct 252 ms 709420 KB Output is correct
3 Correct 248 ms 709444 KB Output is correct
4 Correct 249 ms 709608 KB Output is correct
5 Correct 254 ms 709484 KB Output is correct
6 Correct 249 ms 709476 KB Output is correct
7 Correct 279 ms 709396 KB Output is correct
8 Correct 246 ms 709464 KB Output is correct
9 Correct 249 ms 709448 KB Output is correct
10 Correct 257 ms 709440 KB Output is correct
11 Correct 247 ms 709492 KB Output is correct
12 Correct 266 ms 709476 KB Output is correct
13 Correct 254 ms 709384 KB Output is correct
14 Correct 257 ms 709420 KB Output is correct
15 Correct 251 ms 709428 KB Output is correct
16 Correct 245 ms 709500 KB Output is correct
17 Correct 263 ms 709420 KB Output is correct
18 Correct 253 ms 709560 KB Output is correct
19 Correct 266 ms 709640 KB Output is correct
20 Correct 255 ms 709572 KB Output is correct
21 Correct 266 ms 709676 KB Output is correct
22 Correct 273 ms 709604 KB Output is correct
23 Correct 251 ms 709588 KB Output is correct
24 Correct 294 ms 709696 KB Output is correct
25 Correct 254 ms 709604 KB Output is correct
26 Correct 272 ms 709608 KB Output is correct
27 Correct 269 ms 709816 KB Output is correct
28 Correct 281 ms 709852 KB Output is correct
29 Correct 262 ms 709812 KB Output is correct
30 Correct 277 ms 709784 KB Output is correct
31 Correct 276 ms 709880 KB Output is correct
32 Correct 273 ms 709812 KB Output is correct
33 Correct 562 ms 713556 KB Output is correct
34 Correct 538 ms 713656 KB Output is correct
35 Correct 508 ms 713572 KB Output is correct
36 Correct 616 ms 713540 KB Output is correct
37 Correct 589 ms 713536 KB Output is correct
38 Correct 583 ms 713596 KB Output is correct
39 Correct 1368 ms 713536 KB Output is correct
40 Correct 1461 ms 713532 KB Output is correct
41 Correct 1396 ms 713536 KB Output is correct
42 Correct 516 ms 713536 KB Output is correct
43 Correct 575 ms 713560 KB Output is correct
44 Correct 582 ms 713524 KB Output is correct
45 Correct 547 ms 713528 KB Output is correct
46 Correct 569 ms 713568 KB Output is correct
47 Correct 553 ms 713532 KB Output is correct
48 Correct 542 ms 713560 KB Output is correct
49 Correct 608 ms 713628 KB Output is correct
50 Correct 563 ms 713524 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 709584 KB Output is correct
2 Correct 252 ms 709420 KB Output is correct
3 Correct 248 ms 709444 KB Output is correct
4 Correct 249 ms 709608 KB Output is correct
5 Correct 254 ms 709484 KB Output is correct
6 Correct 249 ms 709476 KB Output is correct
7 Correct 279 ms 709396 KB Output is correct
8 Correct 246 ms 709464 KB Output is correct
9 Correct 249 ms 709448 KB Output is correct
10 Correct 257 ms 709440 KB Output is correct
11 Correct 247 ms 709492 KB Output is correct
12 Correct 266 ms 709476 KB Output is correct
13 Correct 254 ms 709384 KB Output is correct
14 Correct 257 ms 709420 KB Output is correct
15 Correct 251 ms 709428 KB Output is correct
16 Correct 245 ms 709500 KB Output is correct
17 Correct 263 ms 709420 KB Output is correct
18 Correct 253 ms 709560 KB Output is correct
19 Correct 266 ms 709640 KB Output is correct
20 Correct 255 ms 709572 KB Output is correct
21 Correct 266 ms 709676 KB Output is correct
22 Correct 273 ms 709604 KB Output is correct
23 Correct 251 ms 709588 KB Output is correct
24 Correct 294 ms 709696 KB Output is correct
25 Correct 254 ms 709604 KB Output is correct
26 Correct 272 ms 709608 KB Output is correct
27 Correct 999 ms 722248 KB Output is correct
28 Correct 970 ms 722116 KB Output is correct
29 Correct 1004 ms 721832 KB Output is correct
30 Correct 958 ms 722112 KB Output is correct
31 Correct 726 ms 721844 KB Output is correct
32 Correct 940 ms 721956 KB Output is correct
33 Correct 799 ms 722136 KB Output is correct
34 Correct 875 ms 721916 KB Output is correct
35 Correct 256 ms 709468 KB Output is correct
36 Correct 594 ms 713792 KB Output is correct
37 Correct 1442 ms 722124 KB Output is correct
38 Correct 1442 ms 722124 KB Output is correct
39 Correct 1394 ms 721840 KB Output is correct
40 Correct 765 ms 716132 KB Output is correct
41 Correct 482 ms 712900 KB Output is correct
42 Correct 287 ms 710300 KB Output is correct
43 Correct 1466 ms 722120 KB Output is correct
44 Correct 1320 ms 722124 KB Output is correct
45 Correct 1351 ms 721976 KB Output is correct
46 Correct 1271 ms 722120 KB Output is correct
47 Correct 1161 ms 721736 KB Output is correct
48 Correct 1300 ms 722116 KB Output is correct
49 Correct 1280 ms 722172 KB Output is correct
50 Correct 1079 ms 721476 KB Output is correct
51 Correct 269 ms 709816 KB Output is correct
52 Correct 281 ms 709852 KB Output is correct
53 Correct 262 ms 709812 KB Output is correct
54 Correct 277 ms 709784 KB Output is correct
55 Correct 276 ms 709880 KB Output is correct
56 Correct 273 ms 709812 KB Output is correct
57 Correct 562 ms 713556 KB Output is correct
58 Correct 538 ms 713656 KB Output is correct
59 Correct 508 ms 713572 KB Output is correct
60 Correct 616 ms 713540 KB Output is correct
61 Correct 589 ms 713536 KB Output is correct
62 Correct 583 ms 713596 KB Output is correct
63 Correct 1368 ms 713536 KB Output is correct
64 Correct 1461 ms 713532 KB Output is correct
65 Correct 1396 ms 713536 KB Output is correct
66 Correct 516 ms 713536 KB Output is correct
67 Correct 575 ms 713560 KB Output is correct
68 Correct 582 ms 713524 KB Output is correct
69 Correct 547 ms 713528 KB Output is correct
70 Correct 569 ms 713568 KB Output is correct
71 Correct 553 ms 713532 KB Output is correct
72 Correct 542 ms 713560 KB Output is correct
73 Correct 608 ms 713628 KB Output is correct
74 Correct 563 ms 713524 KB Output is correct
75 Correct 1115 ms 721852 KB Output is correct
76 Correct 1053 ms 722352 KB Output is correct
77 Correct 1085 ms 722104 KB Output is correct
78 Correct 1076 ms 721972 KB Output is correct
79 Correct 1347 ms 721972 KB Output is correct
80 Correct 1073 ms 721856 KB Output is correct
81 Correct 1426 ms 721980 KB Output is correct
82 Correct 1449 ms 721972 KB Output is correct
83 Correct 1426 ms 721988 KB Output is correct
84 Correct 1453 ms 721984 KB Output is correct
85 Correct 1395 ms 721980 KB Output is correct
86 Correct 1444 ms 721984 KB Output is correct
87 Correct 1417 ms 721980 KB Output is correct
88 Execution timed out 3123 ms 720112 KB Time limit exceeded
89 Halted 0 ms 0 KB -