oj.uz

Submission #318520

# Submission time Handle Problem Language Result Execution time Memory
318520 2020-11-02T08:38:56 Z IloveN Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 348884 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 x)
    {
        for (int i=pos;i<(int)bit[id].size();i+=(i&-i)) bit[id][i]+=x;
    }

    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=lg[id];i>=0;i--)
            if (res+(1<<i)<=len && sum+bit[id][res+(1<<i)]<=x) res+=(1<<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];
        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,-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);
    }

    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 122468 KB Output is correct
3 Correct 86 ms 122468 KB Output is correct
4 Correct 83 ms 122468 KB Output is correct
5 Correct 84 ms 122468 KB Output is correct
6 Correct 84 ms 122596 KB Output is correct
7 Correct 83 ms 122596 KB Output is correct
8 Correct 82 ms 122468 KB Output is correct
9 Correct 84 ms 122576 KB Output is correct
10 Correct 84 ms 122596 KB Output is correct
11 Correct 83 ms 122468 KB Output is correct
12 Correct 82 ms 122468 KB Output is correct
13 Correct 87 ms 122468 KB Output is correct
14 Correct 83 ms 122468 KB Output is correct
15 Correct 84 ms 122468 KB Output is correct
16 Correct 85 ms 122980 KB Output is correct
17 Correct 86 ms 122980 KB Output is correct
18 Correct 85 ms 123236 KB Output is correct
19 Correct 99 ms 125412 KB Output is correct
20 Correct 100 ms 125412 KB Output is correct
21 Correct 101 ms 125412 KB Output is correct
22 Correct 106 ms 125412 KB Output is correct
23 Correct 105 ms 125284 KB Output is correct
24 Correct 102 ms 125284 KB Output is correct
25 Correct 102 ms 125284 KB Output is correct
26 Correct 104 ms 125284 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1420 ms 348884 KB Output is correct
2 Correct 1432 ms 347356 KB Output is correct
3 Correct 1435 ms 347732 KB Output is correct
4 Correct 1422 ms 348884 KB Output is correct
5 Correct 1495 ms 345444 KB Output is correct
6 Correct 1963 ms 345444 KB Output is correct
7 Correct 1564 ms 345444 KB Output is correct
8 Correct 1646 ms 345316 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 122468 KB Output is correct
2 Correct 1020 ms 194148 KB Output is correct
3 Execution timed out 3087 ms 345716 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 3044 ms 345944 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 122468 KB Output is correct
3 Correct 86 ms 122468 KB Output is correct
4 Correct 83 ms 122468 KB Output is correct
5 Correct 84 ms 122468 KB Output is correct
6 Correct 84 ms 122596 KB Output is correct
7 Correct 83 ms 122596 KB Output is correct
8 Correct 82 ms 122468 KB Output is correct
9 Correct 84 ms 122576 KB Output is correct
10 Correct 84 ms 122596 KB Output is correct
11 Correct 83 ms 122468 KB Output is correct
12 Correct 82 ms 122468 KB Output is correct
13 Correct 87 ms 122468 KB Output is correct
14 Correct 83 ms 122468 KB Output is correct
15 Correct 84 ms 122468 KB Output is correct
16 Correct 85 ms 122980 KB Output is correct
17 Correct 86 ms 122980 KB Output is correct
18 Correct 85 ms 123236 KB Output is correct
19 Correct 99 ms 125412 KB Output is correct
20 Correct 100 ms 125412 KB Output is correct
21 Correct 101 ms 125412 KB Output is correct
22 Correct 106 ms 125412 KB Output is correct
23 Correct 105 ms 125284 KB Output is correct
24 Correct 102 ms 125284 KB Output is correct
25 Correct 102 ms 125284 KB Output is correct
26 Correct 104 ms 125284 KB Output is correct
27 Correct 121 ms 128484 KB Output is correct
28 Correct 121 ms 128484 KB Output is correct
29 Correct 121 ms 128484 KB Output is correct
30 Correct 134 ms 128548 KB Output is correct
31 Correct 132 ms 128356 KB Output is correct
32 Correct 131 ms 128356 KB Output is correct
33 Correct 695 ms 195036 KB Output is correct
34 Correct 684 ms 195036 KB Output is correct
35 Correct 690 ms 195164 KB Output is correct
36 Correct 953 ms 194148 KB Output is correct
37 Correct 963 ms 194148 KB Output is correct
38 Correct 974 ms 194148 KB Output is correct
39 Correct 1048 ms 194772 KB Output is correct
40 Correct 1028 ms 194772 KB Output is correct
41 Correct 1039 ms 195028 KB Output is correct
42 Correct 818 ms 194020 KB Output is correct
43 Correct 825 ms 193892 KB Output is correct
44 Correct 821 ms 194020 KB Output is correct
45 Correct 814 ms 194076 KB Output is correct
46 Correct 814 ms 194020 KB Output is correct
47 Correct 817 ms 193892 KB Output is correct
48 Correct 818 ms 194020 KB Output is correct
49 Correct 815 ms 194020 KB Output is correct
50 Correct 816 ms 193892 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 122468 KB Output is correct
3 Correct 86 ms 122468 KB Output is correct
4 Correct 83 ms 122468 KB Output is correct
5 Correct 84 ms 122468 KB Output is correct
6 Correct 84 ms 122596 KB Output is correct
7 Correct 83 ms 122596 KB Output is correct
8 Correct 82 ms 122468 KB Output is correct
9 Correct 84 ms 122576 KB Output is correct
10 Correct 84 ms 122596 KB Output is correct
11 Correct 83 ms 122468 KB Output is correct
12 Correct 82 ms 122468 KB Output is correct
13 Correct 87 ms 122468 KB Output is correct
14 Correct 83 ms 122468 KB Output is correct
15 Correct 84 ms 122468 KB Output is correct
16 Correct 85 ms 122980 KB Output is correct
17 Correct 86 ms 122980 KB Output is correct
18 Correct 85 ms 123236 KB Output is correct
19 Correct 99 ms 125412 KB Output is correct
20 Correct 100 ms 125412 KB Output is correct
21 Correct 101 ms 125412 KB Output is correct
22 Correct 106 ms 125412 KB Output is correct
23 Correct 105 ms 125284 KB Output is correct
24 Correct 102 ms 125284 KB Output is correct
25 Correct 102 ms 125284 KB Output is correct
26 Correct 104 ms 125284 KB Output is correct
27 Correct 1420 ms 348884 KB Output is correct
28 Correct 1432 ms 347356 KB Output is correct
29 Correct 1435 ms 347732 KB Output is correct
30 Correct 1422 ms 348884 KB Output is correct
31 Correct 1495 ms 345444 KB Output is correct
32 Correct 1963 ms 345444 KB Output is correct
33 Correct 1564 ms 345444 KB Output is correct
34 Correct 1646 ms 345316 KB Output is correct
35 Correct 85 ms 122468 KB Output is correct
36 Correct 1020 ms 194148 KB Output is correct
37 Execution timed out 3087 ms 345716 KB Time limit exceeded
38 Halted 0 ms 0 KB -