oj.uz

Submission #318532

# Submission time Handle Problem Language Result Execution time Memory
318532 2020-11-02T09:25:13 Z IloveN Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 404824 KB 
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=3e5+10;
const ll inf=1e9;
struct circle{int x,y,r,id;};

circle a[N];
int n;

struct segment_tree_2d
{
    vi pre[N*4],nex[N*4],pos_in[N],bit[N*4];
    vector<pii> val[N*4];
    pii arr[N];
    int len,lg[N*4];

    void add(int id,int pos,int len)
    {
        for (int i=pos;i<=len;i+=(i&-i)) --bit[id][i];
    }

    int get(int id,int pos)
    {
        int res=0;
        for (int i=pos;i;i-=(i&-i)) res+=bit[id][i];
        return res;
    }

    int lw(int id,int x)
    {
        int sum=0,res=0,len=val[id].size();
        for (int i=(1<<lg[id]);i;i>>=1)
            if ((res | i)<=len && sum+bit[id][res | i]<=x) res|=i,sum+=bit[id][res];
        return res+1;
    }

    void build(int id,int l,int r)
    {
        if (l==r)
        {
            val[id].eb(arr[l]);
            bit[id].resize(2,1);
            pre[id].eb(-1);
            nex[id].eb(2);
            pos_in[l].eb(0);
            return;
        }
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        val[id].resize(val[id*2].size()+val[id*2+1].size());
        merge(all(val[id*2]),all(val[id*2+1]),val[id].begin());
        int len=val[id].size();
        pre[id].resize(len);
        nex[id].resize(len);
        for (int i=0;i<len;i++) pre[id][i]=i-1,nex[id][i]=i+1,pos_in[val[id][i].se].eb(i);
        bit[id].resize(val[id].size()+1,0);
        for (int i=1;i<=len;i++) bit[id][i]=(i&-i);
        while (len>1) len>>=1,lg[id]++;
    }

    void input(pii ar[],int siz)
    {
        len=siz;
        for (int i=1;i<=len;i++) arr[i]=ar[i];
        for (int i=1;i<=len*4;i++) pos_in[i].reserve(20);
        build(1,1,len);
    }

    void update(int id,int l,int r,int v,int layer)
    {
        int pos=pos_in[v][layer];
        add(id,pos+1,val[id].size());
        if (pre[id][pos]>-1) nex[id][pre[id][pos]]=nex[id][pos];
        if (nex[id][pos]<(int)val[id].size()) pre[id][nex[id][pos]]=pre[id][pos];
        if (l==r) return;
        int mid=(l+r)/2;
        if (v<=mid) update(id*2,l,mid,v,layer-1);
        else update(id*2+1,mid+1,r,v,layer-1);
    }

    vi pot;

    void searc(int id,int l,int r,int u,int v,int y1,int y2)
    {
        if (l>v || r<u) return;
        if (u<=l && r<=v)
        {
            int pos=lower_bound(all(val[id]),mp(y1,0))-val[id].begin();
            if (pos>(int)val[id].size()) return;
            pos=lw(id,get(id,pos))-1;
            if (pos<0) return;
            while (pos<(int)val[id].size() && val[id][pos].fi<=y2)
            {
                pot.eb(val[id][pos].se);
                pos=nex[id][pos];
            }
            return;
        }
        int mid=(l+r)/2;
        searc(id*2,l,mid,u,v,y1,y2);
        searc(id*2+1,mid+1,r,u,v,y1,y2);
    }

    vi find_pot(int u,int v,int y1,int y2)
    {
        pot.clear();
        if (u<=v) searc(1,1,n,u,v,y1,y2);
        return pot;
    }

    void del(vi &vt)
    {
        for (int x : vt) update(1,1,n,x,pos_in[x].size()-1);
    }
} seg;

void read()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].r,a[i].id=i;
}

bool cmp(circle &obj1, circle &obj2) { return (obj1.r>obj2.r) || ((obj1.r==obj2.r) && (obj1.id<obj2.id));}
pii X[N],Y[N];
int ans[N];

ll sqr(ll x) { return x*x;}

bool intersect(int i,int j)
{
    return sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)<=sqr(a[i].r+a[j].r);
}

void process()
{
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++) X[i]=mp(a[i].x,i);
    sort(X+1,X+n+1);
    for (int i=1;i<=n;i++) Y[i]=mp(a[X[i].se].y,i);
    seg.input(Y,n);
    for (int i=1;i<=n;i++)
    if (ans[a[i].id]==0)
    {
        int x1=max(-inf,(ll)a[i].x-a[i].r*2),x2=min(inf,(ll)a[i].x+a[i].r*2);
        int y1=max(-inf,(ll)a[i].y-a[i].r*2),y2=min(inf,(ll)a[i].y+a[i].r*2);
        int u=lower_bound(X+1,X+n+1,mp(x1,0))-X;
        int v=upper_bound(X+1,X+n+1,mp(x2,n+2))-X-1;
        vi vt=seg.find_pot(u,v,y1,y2);
        vi vt2;
        for (int x : vt)
            if (intersect(i,X[x].se)) ans[a[X[x].se].id]=a[i].id,vt2.eb(x);
        seg.del(vt2);
    }
    for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
}

int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    read();
    process();
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122468 KB Output is correct
2 Correct 83 ms 122472 KB Output is correct
3 Correct 85 ms 122468 KB Output is correct
4 Correct 82 ms 122468 KB Output is correct
5 Correct 83 ms 122472 KB Output is correct
6 Correct 83 ms 122596 KB Output is correct
7 Correct 83 ms 122680 KB Output is correct
8 Correct 86 ms 122600 KB Output is correct
9 Correct 84 ms 122596 KB Output is correct
10 Correct 84 ms 122600 KB Output is correct
11 Correct 84 ms 122596 KB Output is correct
12 Correct 82 ms 122724 KB Output is correct
13 Correct 84 ms 122596 KB Output is correct
14 Correct 84 ms 122596 KB Output is correct
15 Correct 84 ms 122596 KB Output is correct
16 Correct 86 ms 123364 KB Output is correct
17 Correct 86 ms 123364 KB Output is correct
18 Correct 87 ms 123364 KB Output is correct
19 Correct 99 ms 127076 KB Output is correct
20 Correct 100 ms 127076 KB Output is correct
21 Correct 98 ms 127076 KB Output is correct
22 Correct 104 ms 126948 KB Output is correct
23 Correct 106 ms 126948 KB Output is correct
24 Correct 101 ms 126948 KB Output is correct
25 Correct 101 ms 126948 KB Output is correct
26 Correct 104 ms 126948 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1233 ms 404528 KB Output is correct
2 Correct 1232 ms 402796 KB Output is correct
3 Correct 1244 ms 403440 KB Output is correct
4 Correct 1242 ms 404824 KB Output is correct
5 Correct 1302 ms 398948 KB Output is correct
6 Correct 1772 ms 399076 KB Output is correct
7 Correct 1350 ms 399204 KB Output is correct
8 Correct 1452 ms 399060 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122468 KB Output is correct
2 Correct 984 ms 215488 KB Output is correct
3 Execution timed out 3110 ms 402660 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 399916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122468 KB Output is correct
2 Correct 83 ms 122472 KB Output is correct
3 Correct 85 ms 122468 KB Output is correct
4 Correct 82 ms 122468 KB Output is correct
5 Correct 83 ms 122472 KB Output is correct
6 Correct 83 ms 122596 KB Output is correct
7 Correct 83 ms 122680 KB Output is correct
8 Correct 86 ms 122600 KB Output is correct
9 Correct 84 ms 122596 KB Output is correct
10 Correct 84 ms 122600 KB Output is correct
11 Correct 84 ms 122596 KB Output is correct
12 Correct 82 ms 122724 KB Output is correct
13 Correct 84 ms 122596 KB Output is correct
14 Correct 84 ms 122596 KB Output is correct
15 Correct 84 ms 122596 KB Output is correct
16 Correct 86 ms 123364 KB Output is correct
17 Correct 86 ms 123364 KB Output is correct
18 Correct 87 ms 123364 KB Output is correct
19 Correct 99 ms 127076 KB Output is correct
20 Correct 100 ms 127076 KB Output is correct
21 Correct 98 ms 127076 KB Output is correct
22 Correct 104 ms 126948 KB Output is correct
23 Correct 106 ms 126948 KB Output is correct
24 Correct 101 ms 126948 KB Output is correct
25 Correct 101 ms 126948 KB Output is correct
26 Correct 104 ms 126948 KB Output is correct
27 Correct 119 ms 131812 KB Output is correct
28 Correct 126 ms 131812 KB Output is correct
29 Correct 121 ms 131848 KB Output is correct
30 Correct 132 ms 131588 KB Output is correct
31 Correct 130 ms 131556 KB Output is correct
32 Correct 130 ms 131556 KB Output is correct
33 Correct 625 ms 216796 KB Output is correct
34 Correct 634 ms 216796 KB Output is correct
35 Correct 637 ms 216732 KB Output is correct
36 Correct 893 ms 215396 KB Output is correct
37 Correct 899 ms 215396 KB Output is correct
38 Correct 911 ms 215396 KB Output is correct
39 Correct 960 ms 214596 KB Output is correct
40 Correct 964 ms 214584 KB Output is correct
41 Correct 982 ms 214612 KB Output is correct
42 Correct 752 ms 214244 KB Output is correct
43 Correct 789 ms 215396 KB Output is correct
44 Correct 782 ms 215396 KB Output is correct
45 Correct 779 ms 215524 KB Output is correct
46 Correct 780 ms 215396 KB Output is correct
47 Correct 777 ms 215396 KB Output is correct
48 Correct 778 ms 215416 KB Output is correct
49 Correct 783 ms 215396 KB Output is correct
50 Correct 784 ms 215396 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122468 KB Output is correct
2 Correct 83 ms 122472 KB Output is correct
3 Correct 85 ms 122468 KB Output is correct
4 Correct 82 ms 122468 KB Output is correct
5 Correct 83 ms 122472 KB Output is correct
6 Correct 83 ms 122596 KB Output is correct
7 Correct 83 ms 122680 KB Output is correct
8 Correct 86 ms 122600 KB Output is correct
9 Correct 84 ms 122596 KB Output is correct
10 Correct 84 ms 122600 KB Output is correct
11 Correct 84 ms 122596 KB Output is correct
12 Correct 82 ms 122724 KB Output is correct
13 Correct 84 ms 122596 KB Output is correct
14 Correct 84 ms 122596 KB Output is correct
15 Correct 84 ms 122596 KB Output is correct
16 Correct 86 ms 123364 KB Output is correct
17 Correct 86 ms 123364 KB Output is correct
18 Correct 87 ms 123364 KB Output is correct
19 Correct 99 ms 127076 KB Output is correct
20 Correct 100 ms 127076 KB Output is correct
21 Correct 98 ms 127076 KB Output is correct
22 Correct 104 ms 126948 KB Output is correct
23 Correct 106 ms 126948 KB Output is correct
24 Correct 101 ms 126948 KB Output is correct
25 Correct 101 ms 126948 KB Output is correct
26 Correct 104 ms 126948 KB Output is correct
27 Correct 1233 ms 404528 KB Output is correct
28 Correct 1232 ms 402796 KB Output is correct
29 Correct 1244 ms 403440 KB Output is correct
30 Correct 1242 ms 404824 KB Output is correct
31 Correct 1302 ms 398948 KB Output is correct
32 Correct 1772 ms 399076 KB Output is correct
33 Correct 1350 ms 399204 KB Output is correct
34 Correct 1452 ms 399060 KB Output is correct
35 Correct 83 ms 122468 KB Output is correct
36 Correct 984 ms 215488 KB Output is correct
37 Execution timed out 3110 ms 402660 KB Time limit exceeded
38 Halted 0 ms 0 KB -