oj.uz

Submission #318496

# Submission time Handle Problem Language Result Execution time Memory
318496 2020-11-02T07:27:30 Z IloveN Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 351464 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];
    vector<bool> it[N*4];
    vector<pii> val[N*4];
    pii arr[N];
    int len;

    /*void build_sub(int sub,int id,int l,int r)
    {
        if (l==r)
        {
            it[sub][id]=true;
            return;
        }
        int mid=(l+r)/2;
        build_sub(sub,id*2,l,mid);
        build_sub(sub,id*2+1,mid+1,r);
        it[sub][id]=true;
    }*/

    void build(int id,int l,int r)
    {
        if (l==r)
        {
            val[id].eb(arr[l]);
            it[id].resize(5,true);
            //build_sub(id,1,1,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());
        pre[id].resize(val[id].size());
        nex[id].resize(val[id].size());
        for (int i=0;i<(int)val[id].size();i++) pre[id][i]=i-1,nex[id][i]=i+1,pos_in[val[id][i].se].eb(i);
        it[id].resize(val[id].size()*4+1,true);
        //build_sub(id,1,1,val[id].size());
    }

    void input(pii ar[],int siz)
    {
        len=siz;
        for (int i=1;i<=len;i++) arr[i]=ar[i];
        build(1,1,len);
    }

    void update_sub(int sub,int id,int l,int r,int v)
    {
        if (l==r)
        {
            it[sub][id]=false;
            return;
        }
        int mid=(l+r)/2;
        if (v<=mid) update_sub(sub,id*2,l,mid,v);
        else update_sub(sub,id*2+1,mid+1,r,v);
        it[sub][id]=(it[sub][id*2] | it[sub][id*2+1]);
    }

    void update(int id,int l,int r,int v,int layer)
    {
        int pos=pos_in[v][layer];
        update_sub(id,1,1,val[id].size(),pos+1);
        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);
    }

    int lw_sub(int sub,int id,int l,int r,int v)
    {
        if (r<v || !it[sub][id]) return -1;
        if (l==r) return l;
        int mid=(l+r)/2;
        int res=lw_sub(sub,id*2,l,mid,v);
        if (res==-1) return lw_sub(sub,id*2+1,mid+1,r,v);
        return res;
    }

    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()+1;
            pos=lw_sub(id,1,1,val[id].size(),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);
    read();
    process();
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 141284 KB Output is correct
2 Correct 95 ms 141284 KB Output is correct
3 Correct 94 ms 141288 KB Output is correct
4 Correct 95 ms 141284 KB Output is correct
5 Correct 95 ms 141252 KB Output is correct
6 Correct 97 ms 141284 KB Output is correct
7 Correct 96 ms 141284 KB Output is correct
8 Correct 94 ms 141356 KB Output is correct
9 Correct 95 ms 141284 KB Output is correct
10 Correct 94 ms 141212 KB Output is correct
11 Correct 95 ms 141284 KB Output is correct
12 Correct 95 ms 141312 KB Output is correct
13 Correct 95 ms 141284 KB Output is correct
14 Correct 97 ms 141412 KB Output is correct
15 Correct 95 ms 141284 KB Output is correct
16 Correct 98 ms 141924 KB Output is correct
17 Correct 99 ms 141796 KB Output is correct
18 Correct 100 ms 141796 KB Output is correct
19 Correct 122 ms 144100 KB Output is correct
20 Correct 117 ms 144100 KB Output is correct
21 Correct 115 ms 144100 KB Output is correct
22 Correct 120 ms 143972 KB Output is correct
23 Correct 123 ms 143972 KB Output is correct
24 Correct 118 ms 143968 KB Output is correct
25 Correct 120 ms 143972 KB Output is correct
26 Correct 118 ms 144024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1803 ms 351464 KB Output is correct
2 Correct 1815 ms 348172 KB Output is correct
3 Correct 1825 ms 348520 KB Output is correct
4 Correct 1806 ms 349524 KB Output is correct
5 Correct 1926 ms 348132 KB Output is correct
6 Correct 2601 ms 348352 KB Output is correct
7 Correct 2004 ms 347868 KB Output is correct
8 Correct 2130 ms 348004 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 141284 KB Output is correct
2 Correct 1285 ms 208996 KB Output is correct
3 Execution timed out 3122 ms 346212 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 3075 ms 345772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 141284 KB Output is correct
2 Correct 95 ms 141284 KB Output is correct
3 Correct 94 ms 141288 KB Output is correct
4 Correct 95 ms 141284 KB Output is correct
5 Correct 95 ms 141252 KB Output is correct
6 Correct 97 ms 141284 KB Output is correct
7 Correct 96 ms 141284 KB Output is correct
8 Correct 94 ms 141356 KB Output is correct
9 Correct 95 ms 141284 KB Output is correct
10 Correct 94 ms 141212 KB Output is correct
11 Correct 95 ms 141284 KB Output is correct
12 Correct 95 ms 141312 KB Output is correct
13 Correct 95 ms 141284 KB Output is correct
14 Correct 97 ms 141412 KB Output is correct
15 Correct 95 ms 141284 KB Output is correct
16 Correct 98 ms 141924 KB Output is correct
17 Correct 99 ms 141796 KB Output is correct
18 Correct 100 ms 141796 KB Output is correct
19 Correct 122 ms 144100 KB Output is correct
20 Correct 117 ms 144100 KB Output is correct
21 Correct 115 ms 144100 KB Output is correct
22 Correct 120 ms 143972 KB Output is correct
23 Correct 123 ms 143972 KB Output is correct
24 Correct 118 ms 143968 KB Output is correct
25 Correct 120 ms 143972 KB Output is correct
26 Correct 118 ms 144024 KB Output is correct
27 Correct 141 ms 147168 KB Output is correct
28 Correct 140 ms 147172 KB Output is correct
29 Correct 139 ms 147172 KB Output is correct
30 Correct 162 ms 146916 KB Output is correct
31 Correct 157 ms 146916 KB Output is correct
32 Correct 154 ms 146912 KB Output is correct
33 Correct 874 ms 210012 KB Output is correct
34 Correct 887 ms 210012 KB Output is correct
35 Correct 885 ms 210016 KB Output is correct
36 Correct 1207 ms 208916 KB Output is correct
37 Correct 1235 ms 208972 KB Output is correct
38 Correct 1279 ms 209124 KB Output is correct
39 Correct 1257 ms 208852 KB Output is correct
40 Correct 1231 ms 208976 KB Output is correct
41 Correct 1215 ms 208872 KB Output is correct
42 Correct 1016 ms 208040 KB Output is correct
43 Correct 1049 ms 208868 KB Output is correct
44 Correct 1022 ms 208996 KB Output is correct
45 Correct 1029 ms 208868 KB Output is correct
46 Correct 1043 ms 208740 KB Output is correct
47 Correct 1031 ms 208868 KB Output is correct
48 Correct 1041 ms 208740 KB Output is correct
49 Correct 1034 ms 208740 KB Output is correct
50 Correct 1034 ms 208836 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 141284 KB Output is correct
2 Correct 95 ms 141284 KB Output is correct
3 Correct 94 ms 141288 KB Output is correct
4 Correct 95 ms 141284 KB Output is correct
5 Correct 95 ms 141252 KB Output is correct
6 Correct 97 ms 141284 KB Output is correct
7 Correct 96 ms 141284 KB Output is correct
8 Correct 94 ms 141356 KB Output is correct
9 Correct 95 ms 141284 KB Output is correct
10 Correct 94 ms 141212 KB Output is correct
11 Correct 95 ms 141284 KB Output is correct
12 Correct 95 ms 141312 KB Output is correct
13 Correct 95 ms 141284 KB Output is correct
14 Correct 97 ms 141412 KB Output is correct
15 Correct 95 ms 141284 KB Output is correct
16 Correct 98 ms 141924 KB Output is correct
17 Correct 99 ms 141796 KB Output is correct
18 Correct 100 ms 141796 KB Output is correct
19 Correct 122 ms 144100 KB Output is correct
20 Correct 117 ms 144100 KB Output is correct
21 Correct 115 ms 144100 KB Output is correct
22 Correct 120 ms 143972 KB Output is correct
23 Correct 123 ms 143972 KB Output is correct
24 Correct 118 ms 143968 KB Output is correct
25 Correct 120 ms 143972 KB Output is correct
26 Correct 118 ms 144024 KB Output is correct
27 Correct 1803 ms 351464 KB Output is correct
28 Correct 1815 ms 348172 KB Output is correct
29 Correct 1825 ms 348520 KB Output is correct
30 Correct 1806 ms 349524 KB Output is correct
31 Correct 1926 ms 348132 KB Output is correct
32 Correct 2601 ms 348352 KB Output is correct
33 Correct 2004 ms 347868 KB Output is correct
34 Correct 2130 ms 348004 KB Output is correct
35 Correct 97 ms 141284 KB Output is correct
36 Correct 1285 ms 208996 KB Output is correct
37 Execution timed out 3122 ms 346212 KB Time limit exceeded
38 Halted 0 ms 0 KB -