oj.uz

Submission #499270

# Submission time Handle Problem Language Result Execution time Memory
499270 2021-12-27T17:49:02 Z _martynas Circle selection (APIO18_circle_selection) C++14
87 / 100
 3000 ms 661040 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MOD = 1e9+7;

const int MAX_N = 3e5+5;

int n;
ll X[MAX_N], Y[MAX_N], R[MAX_N];
int P[MAX_N];
bool visited[MAX_N];
int Inh[MAX_N];

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

    LLNode()
    {
    }

    LLNode(int val)
        : idx(val)
    {
    }
};

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

    Quad()
    {
    }

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

    void add(ll x, ll y, 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 = new LLNode(idx);
            }
            else {
                LLNode* temp = new LLNode(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] = new Quad(l, midH, bot, midV);
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > midV)) {
                    childs[1] = new Quad(midH+1, r, bot, midV);
                }
                else if(childs[2] == nullptr && !(x < l || x > midH || y < midV+1 || y > top)) {
                    childs[2] = new Quad(l, midH, midV+1, top);
                }
                else if(childs[3] == nullptr && !(x < midH+1 || x > r || y < midV+1 || y > top)) {
                    childs[3] = new Quad(midH+1, r, midV+1, top);
                }
            }
            else if(l != r) {
                if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > top)) {
                    childs[0] = new Quad(l, midH, bot, midV);
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > top)) {
                    childs[1] = new Quad(midH+1, r, bot, top);
                }
            }
            else if(top != bot) {
                if(childs[0] == nullptr && !(x < l || x > r || y < bot || y > midV)) {
                    childs[0] = new Quad(l, r, bot, midV);
                }
                else if(childs[1] == nullptr && !(x < l || x > r || y < midV+1 || y > top)) {
                    childs[1] = new Quad(l, r, midV+1, top);
                }
            }

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

    void setInRange(ll x, ll y, ll radius, 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 &&
                (R[idx]+R[llnode->idx])*(R[idx]+R[llnode->idx])
                >= llabs(X[idx]-X[llnode->idx])*llabs(X[idx]-X[llnode->idx])
                +llabs(Y[idx]-Y[llnode->idx])*llabs(Y[idx]-Y[llnode->idx])) {
                P[llnode->idx] = idx;
                visited[llnode->idx] = 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;
    }
};

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

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> X[i] >> Y[i] >> R[i];
    }
    iota(P, P+n, 0);

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

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

    for(int i = 0; i < n; i++) {
        int idx = I[i];
        if(visited[idx]) continue;
        Q.setInRange(X[idx], Y[idx], R[idx], idx);
    }

    for(int i = 0; i < n; i++) {
        cout << 1+P[i] << " ";
    }
    cout << "\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 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 5 ms 2764 KB Output is correct
17 Correct 4 ms 2508 KB Output is correct
18 Correct 5 ms 2508 KB Output is correct
19 Correct 21 ms 11088 KB Output is correct
20 Correct 24 ms 8756 KB Output is correct
21 Correct 26 ms 11804 KB Output is correct
22 Correct 26 ms 11040 KB Output is correct
23 Correct 20 ms 10060 KB Output is correct
24 Correct 24 ms 11300 KB Output is correct
25 Correct 23 ms 12108 KB Output is correct
26 Correct 23 ms 11744 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1207 ms 363500 KB Output is correct
2 Correct 1180 ms 382032 KB Output is correct
3 Correct 1207 ms 361232 KB Output is correct
4 Correct 1195 ms 398532 KB Output is correct
5 Correct 703 ms 74712 KB Output is correct
6 Correct 1060 ms 220548 KB Output is correct
7 Correct 818 ms 144688 KB Output is correct
8 Correct 857 ms 166692 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 553 ms 227876 KB Output is correct
3 Correct 1792 ms 661016 KB Output is correct
4 Correct 1786 ms 661040 KB Output is correct
5 Correct 1682 ms 592004 KB Output is correct
6 Correct 824 ms 319564 KB Output is correct
7 Correct 396 ms 167704 KB Output is correct
8 Correct 73 ms 34372 KB Output is correct
9 Correct 1947 ms 599796 KB Output is correct
10 Correct 1638 ms 620356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1584 ms 605732 KB Output is correct
2 Correct 1528 ms 578476 KB Output is correct
3 Correct 1440 ms 606140 KB Output is correct
4 Correct 1616 ms 624804 KB Output is correct
5 Correct 1576 ms 603248 KB Output is correct
6 Correct 1373 ms 595340 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 5 ms 2764 KB Output is correct
17 Correct 4 ms 2508 KB Output is correct
18 Correct 5 ms 2508 KB Output is correct
19 Correct 21 ms 11088 KB Output is correct
20 Correct 24 ms 8756 KB Output is correct
21 Correct 26 ms 11804 KB Output is correct
22 Correct 26 ms 11040 KB Output is correct
23 Correct 20 ms 10060 KB Output is correct
24 Correct 24 ms 11300 KB Output is correct
25 Correct 23 ms 12108 KB Output is correct
26 Correct 23 ms 11744 KB Output is correct
27 Correct 42 ms 22160 KB Output is correct
28 Correct 47 ms 20996 KB Output is correct
29 Correct 40 ms 21952 KB Output is correct
30 Correct 44 ms 21096 KB Output is correct
31 Correct 43 ms 21084 KB Output is correct
32 Correct 45 ms 21980 KB Output is correct
33 Correct 428 ms 199076 KB Output is correct
34 Correct 438 ms 208204 KB Output is correct
35 Correct 455 ms 203632 KB Output is correct
36 Correct 504 ms 201908 KB Output is correct
37 Correct 529 ms 210688 KB Output is correct
38 Correct 522 ms 205232 KB Output is correct
39 Correct 949 ms 23776 KB Output is correct
40 Correct 969 ms 23772 KB Output is correct
41 Correct 1097 ms 23712 KB Output is correct
42 Correct 351 ms 91108 KB Output is correct
43 Correct 461 ms 154872 KB Output is correct
44 Correct 467 ms 154896 KB Output is correct
45 Correct 476 ms 154908 KB Output is correct
46 Correct 477 ms 154888 KB Output is correct
47 Correct 467 ms 154892 KB Output is correct
48 Correct 459 ms 154948 KB Output is correct
49 Correct 463 ms 154948 KB Output is correct
50 Correct 457 ms 154912 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 5 ms 2764 KB Output is correct
17 Correct 4 ms 2508 KB Output is correct
18 Correct 5 ms 2508 KB Output is correct
19 Correct 21 ms 11088 KB Output is correct
20 Correct 24 ms 8756 KB Output is correct
21 Correct 26 ms 11804 KB Output is correct
22 Correct 26 ms 11040 KB Output is correct
23 Correct 20 ms 10060 KB Output is correct
24 Correct 24 ms 11300 KB Output is correct
25 Correct 23 ms 12108 KB Output is correct
26 Correct 23 ms 11744 KB Output is correct
27 Correct 1207 ms 363500 KB Output is correct
28 Correct 1180 ms 382032 KB Output is correct
29 Correct 1207 ms 361232 KB Output is correct
30 Correct 1195 ms 398532 KB Output is correct
31 Correct 703 ms 74712 KB Output is correct
32 Correct 1060 ms 220548 KB Output is correct
33 Correct 818 ms 144688 KB Output is correct
34 Correct 857 ms 166692 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 553 ms 227876 KB Output is correct
37 Correct 1792 ms 661016 KB Output is correct
38 Correct 1786 ms 661040 KB Output is correct
39 Correct 1682 ms 592004 KB Output is correct
40 Correct 824 ms 319564 KB Output is correct
41 Correct 396 ms 167704 KB Output is correct
42 Correct 73 ms 34372 KB Output is correct
43 Correct 1947 ms 599796 KB Output is correct
44 Correct 1638 ms 620356 KB Output is correct
45 Correct 1584 ms 605732 KB Output is correct
46 Correct 1528 ms 578476 KB Output is correct
47 Correct 1440 ms 606140 KB Output is correct
48 Correct 1616 ms 624804 KB Output is correct
49 Correct 1576 ms 603248 KB Output is correct
50 Correct 1373 ms 595340 KB Output is correct
51 Correct 42 ms 22160 KB Output is correct
52 Correct 47 ms 20996 KB Output is correct
53 Correct 40 ms 21952 KB Output is correct
54 Correct 44 ms 21096 KB Output is correct
55 Correct 43 ms 21084 KB Output is correct
56 Correct 45 ms 21980 KB Output is correct
57 Correct 428 ms 199076 KB Output is correct
58 Correct 438 ms 208204 KB Output is correct
59 Correct 455 ms 203632 KB Output is correct
60 Correct 504 ms 201908 KB Output is correct
61 Correct 529 ms 210688 KB Output is correct
62 Correct 522 ms 205232 KB Output is correct
63 Correct 949 ms 23776 KB Output is correct
64 Correct 969 ms 23772 KB Output is correct
65 Correct 1097 ms 23712 KB Output is correct
66 Correct 351 ms 91108 KB Output is correct
67 Correct 461 ms 154872 KB Output is correct
68 Correct 467 ms 154896 KB Output is correct
69 Correct 476 ms 154908 KB Output is correct
70 Correct 477 ms 154888 KB Output is correct
71 Correct 467 ms 154892 KB Output is correct
72 Correct 459 ms 154948 KB Output is correct
73 Correct 463 ms 154948 KB Output is correct
74 Correct 457 ms 154912 KB Output is correct
75 Correct 1451 ms 627452 KB Output is correct
76 Correct 1267 ms 485680 KB Output is correct
77 Correct 1304 ms 537600 KB Output is correct
78 Correct 1360 ms 617740 KB Output is correct
79 Correct 1647 ms 632700 KB Output is correct
80 Correct 1359 ms 605964 KB Output is correct
81 Correct 1682 ms 616140 KB Output is correct
82 Correct 1706 ms 620812 KB Output is correct
83 Correct 1694 ms 628432 KB Output is correct
84 Correct 1674 ms 584684 KB Output is correct
85 Correct 1712 ms 636616 KB Output is correct
86 Correct 1719 ms 630976 KB Output is correct
87 Correct 1747 ms 555936 KB Output is correct
88 Execution timed out 3060 ms 71700 KB Time limit exceeded
89 Halted 0 ms 0 KB -