Submission #318528

#	Time	Username	Problem	Language	Result	Execution time	Memory
318528		IloveN	Circle selection (APIO18_circle_selection)	C++14	49 / 100	3067 ms	398016 KiB

circle_selection

#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)
    {
        for (int i=pos;i<(int)bit[id].size();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=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];
        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);
        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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13