oj.uz

Submission #394003

# Submission time Handle Problem Language Result Execution time Memory
394003 2021-04-25T07:31:58 Z 79brue Circle selection (APIO18_circle_selection) C++14
12 / 100
 1457 ms 73588 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Circle{
    ll x, y, r; int idx;
    Circle(ll x, ll y, ll r, int idx): x(x), y(y), r(r), idx(idx){}
    bool touch(const Circle &nxt)const{
        return (x-nxt.x) * (x-nxt.x) + (y-nxt.y) * (y-nxt.y) <= (r+nxt.r) * (r+nxt.r);
    }
    bool operator<(const Circle &nxt)const{
        if(r!=nxt.r) return r>nxt.r;
        return idx<nxt.idx;
    }
};
vector<Circle> vec;
int indexes[300002];

int tree[2400002], lazy[2400002];
void init(int i, int l, int r){
    tree[i] = lazy[i] = 1e9;
    if(l==r) return;
    int m = (l+r)>>1;
    init(i*2, l, m), init(i*2+1, m+1, r);
}

void propagate(int i, int l, int r){
    tree[i] = min(tree[i], lazy[i]);
    if(l!=r){
        lazy[i*2] = min(lazy[i*2], lazy[i]);
        lazy[i*2+1] = min(lazy[i*2+1], lazy[i]);
    }
    lazy[i] = 1e9;
}

void rangeMin(int i, int l, int r, int s, int e, int val){
    propagate(i, l, r);
    if(r<s || e<l) return;
    if(s<=l && r<=e){
        lazy[i] = val;
        propagate(i, l, r);
        return;
    }
    int m = (l+r)>>1;
    rangeMin(i*2, l, m, s, e, val);
    rangeMin(i*2+1, m+1, r, s, e, val);
    tree[i] = min(tree[i*2], tree[i*2+1]);
}

int getVal(int i, int l, int r, int idx){
    propagate(i, l, r);
    if(l==r) return tree[i];
    int m = (l+r)>>1;
    if(idx <= m) return getVal(i*2, l, m, idx);
    return getVal(i*2+1, m+1, r, idx);
}

int n, k;
int ans[300002];
vector<ll> xVec;
map<ll, int> mp;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        ll x, y, r;
        scanf("%lld %lld %lld", &x, &y, &r);
        vec.push_back(Circle(x, y, r, i));
        xVec.push_back(x-r), xVec.push_back(x+r);
    }
    sort(vec.begin(), vec.end());
    for(int i=0; i<n; i++){
        indexes[i] = vec[i].idx;
    }

    sort(xVec.begin(), xVec.end());
    xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
    for(int i=0; i<(int)xVec.size(); i++) mp[xVec[i]] = i;
    k = (int)xVec.size();

    init(1, 0, k-1);
    for(int i=0; i<n; i++){
        Circle c = vec[i];
        int t1 = getVal(1, 0, k-1, mp[c.x-c.r]);
        int t2 = getVal(1, 0, k-1, mp[c.x+c.r]);
        if(t1 == 1e9 && t2 == 1e9){
            ans[c.idx] = c.idx;
            rangeMin(1, 0, k-1, mp[c.x-c.r], mp[c.x+c.r], i);
        }
        else{
            ans[c.idx] = vec[min(t1, t2)].idx;
        }
    }

    for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

Compilation message

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:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1457 ms 72916 KB Output is correct
2 Correct 1403 ms 73040 KB Output is correct
3 Correct 1423 ms 72644 KB Output is correct
4 Correct 1383 ms 73088 KB Output is correct
5 Correct 936 ms 44912 KB Output is correct
6 Correct 1175 ms 72372 KB Output is correct
7 Correct 1171 ms 71848 KB Output is correct
8 Correct 1180 ms 73588 KB Output is correct

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 1188 ms 72580 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 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 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 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -