oj.uz

Submission #318521

# Submission time Handle Problem Language Result Execution time Memory
318521 2020-11-02T08:45:13 Z IloveN Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 348756 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

#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 87 ms 122468 KB Output is correct
2 Correct 88 ms 122468 KB Output is correct
3 Correct 87 ms 122468 KB Output is correct
4 Correct 86 ms 122468 KB Output is correct
5 Correct 90 ms 122468 KB Output is correct
6 Correct 90 ms 122596 KB Output is correct
7 Correct 89 ms 122596 KB Output is correct
8 Correct 91 ms 122596 KB Output is correct
9 Correct 86 ms 122596 KB Output is correct
10 Correct 88 ms 122596 KB Output is correct
11 Correct 90 ms 122468 KB Output is correct
12 Correct 88 ms 122616 KB Output is correct
13 Correct 89 ms 122468 KB Output is correct
14 Correct 88 ms 122628 KB Output is correct
15 Correct 87 ms 122472 KB Output is correct
16 Correct 90 ms 122980 KB Output is correct
17 Correct 90 ms 122980 KB Output is correct
18 Correct 89 ms 122980 KB Output is correct
19 Correct 103 ms 125412 KB Output is correct
20 Correct 109 ms 125412 KB Output is correct
21 Correct 105 ms 125412 KB Output is correct
22 Correct 106 ms 125284 KB Output is correct
23 Correct 112 ms 125280 KB Output is correct
24 Correct 109 ms 125284 KB Output is correct
25 Correct 108 ms 125412 KB Output is correct
26 Correct 108 ms 125284 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1409 ms 348756 KB Output is correct
2 Correct 1431 ms 347104 KB Output is correct
3 Correct 1437 ms 347860 KB Output is correct
4 Correct 1408 ms 348756 KB Output is correct
5 Correct 1520 ms 345276 KB Output is correct
6 Correct 1969 ms 345388 KB Output is correct
7 Correct 1541 ms 345348 KB Output is correct
8 Correct 1632 ms 345456 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 122472 KB Output is correct
2 Correct 1029 ms 194020 KB Output is correct
3 Execution timed out 3084 ms 345932 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 3098 ms 346048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 122468 KB Output is correct
2 Correct 88 ms 122468 KB Output is correct
3 Correct 87 ms 122468 KB Output is correct
4 Correct 86 ms 122468 KB Output is correct
5 Correct 90 ms 122468 KB Output is correct
6 Correct 90 ms 122596 KB Output is correct
7 Correct 89 ms 122596 KB Output is correct
8 Correct 91 ms 122596 KB Output is correct
9 Correct 86 ms 122596 KB Output is correct
10 Correct 88 ms 122596 KB Output is correct
11 Correct 90 ms 122468 KB Output is correct
12 Correct 88 ms 122616 KB Output is correct
13 Correct 89 ms 122468 KB Output is correct
14 Correct 88 ms 122628 KB Output is correct
15 Correct 87 ms 122472 KB Output is correct
16 Correct 90 ms 122980 KB Output is correct
17 Correct 90 ms 122980 KB Output is correct
18 Correct 89 ms 122980 KB Output is correct
19 Correct 103 ms 125412 KB Output is correct
20 Correct 109 ms 125412 KB Output is correct
21 Correct 105 ms 125412 KB Output is correct
22 Correct 106 ms 125284 KB Output is correct
23 Correct 112 ms 125280 KB Output is correct
24 Correct 109 ms 125284 KB Output is correct
25 Correct 108 ms 125412 KB Output is correct
26 Correct 108 ms 125284 KB Output is correct
27 Correct 125 ms 128612 KB Output is correct
28 Correct 132 ms 128484 KB Output is correct
29 Correct 124 ms 128484 KB Output is correct
30 Correct 139 ms 128356 KB Output is correct
31 Correct 135 ms 128356 KB Output is correct
32 Correct 136 ms 128444 KB Output is correct
33 Correct 681 ms 195036 KB Output is correct
34 Correct 672 ms 195040 KB Output is correct
35 Correct 683 ms 195036 KB Output is correct
36 Correct 949 ms 194044 KB Output is correct
37 Correct 954 ms 194144 KB Output is correct
38 Correct 969 ms 194312 KB Output is correct
39 Correct 1014 ms 194900 KB Output is correct
40 Correct 1027 ms 194820 KB Output is correct
41 Correct 1025 ms 195132 KB Output is correct
42 Correct 804 ms 193892 KB Output is correct
43 Correct 821 ms 193892 KB Output is correct
44 Correct 820 ms 194148 KB Output is correct
45 Correct 817 ms 193892 KB Output is correct
46 Correct 822 ms 193892 KB Output is correct
47 Correct 844 ms 193892 KB Output is correct
48 Correct 820 ms 193892 KB Output is correct
49 Correct 818 ms 193892 KB Output is correct
50 Correct 813 ms 193892 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 122468 KB Output is correct
2 Correct 88 ms 122468 KB Output is correct
3 Correct 87 ms 122468 KB Output is correct
4 Correct 86 ms 122468 KB Output is correct
5 Correct 90 ms 122468 KB Output is correct
6 Correct 90 ms 122596 KB Output is correct
7 Correct 89 ms 122596 KB Output is correct
8 Correct 91 ms 122596 KB Output is correct
9 Correct 86 ms 122596 KB Output is correct
10 Correct 88 ms 122596 KB Output is correct
11 Correct 90 ms 122468 KB Output is correct
12 Correct 88 ms 122616 KB Output is correct
13 Correct 89 ms 122468 KB Output is correct
14 Correct 88 ms 122628 KB Output is correct
15 Correct 87 ms 122472 KB Output is correct
16 Correct 90 ms 122980 KB Output is correct
17 Correct 90 ms 122980 KB Output is correct
18 Correct 89 ms 122980 KB Output is correct
19 Correct 103 ms 125412 KB Output is correct
20 Correct 109 ms 125412 KB Output is correct
21 Correct 105 ms 125412 KB Output is correct
22 Correct 106 ms 125284 KB Output is correct
23 Correct 112 ms 125280 KB Output is correct
24 Correct 109 ms 125284 KB Output is correct
25 Correct 108 ms 125412 KB Output is correct
26 Correct 108 ms 125284 KB Output is correct
27 Correct 1409 ms 348756 KB Output is correct
28 Correct 1431 ms 347104 KB Output is correct
29 Correct 1437 ms 347860 KB Output is correct
30 Correct 1408 ms 348756 KB Output is correct
31 Correct 1520 ms 345276 KB Output is correct
32 Correct 1969 ms 345388 KB Output is correct
33 Correct 1541 ms 345348 KB Output is correct
34 Correct 1632 ms 345456 KB Output is correct
35 Correct 86 ms 122472 KB Output is correct
36 Correct 1029 ms 194020 KB Output is correct
37 Execution timed out 3084 ms 345932 KB Time limit exceeded
38 Halted 0 ms 0 KB -