oj.uz

Submission #397484

# Submission time Handle Problem Language Result Execution time Memory
397484 2021-05-02T09:46:22 Z AriaH Circle selection (APIO18_circle_selection) C++17
0 / 100
 1857 ms 330916 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 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(int xl, unsigned int xr, ll yl, ll yr, int &id, int l = 1, int r = n + 1) {
        if (xr <= X[xord[l]] || X[xord[r - 1]] + 1 <= xl) 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, l, md), rc->get(xl, xr, yl, yr, id, 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);
    }
    for (int i = 1; i <= n; i++) printf("%d ", ret[i]);
    printf("\n");
    return 0;
}

Compilation message

circle_selection.cpp: In member function 'void node::get(int, unsigned int, ll, ll, int&, int, int)':
circle_selection.cpp:48:16: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   48 |         if (xr <= X[xord[l]] || X[xord[r - 1]] + 1 <= xl) return;
      |             ~~~^~~~~~~~~~~~~
circle_selection.cpp:49:52: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   49 |         if (xl <= X[xord[l]] && X[xord[r - 1]] + 1 <= xr) {
      |                                 ~~~~~~~~~~~~~~~~~~~^~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d%d%d", &X[i], &Y[i], &R[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1433 ms 330916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1857 ms 330376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -