oj.uz

Submission #354539

# Submission time Handle Problem Language Result Execution time Memory
354539 2021-01-22T03:41:38 Z IloveN Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 404824 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 len)
    {
        for (int i=pos;i<=len;i+=(i&-i)) --bit[id][i];
    }

    int get(int id,int x,int len)
    {
        int res=0,pos=0;
        for (int i=(1<<lg[id]);i;i>>=1)
            if ((pos | i)<=len && val[id][(pos | i) - 1].fi<=x) pos|=i,res+=bit[id][pos];
        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=lw(id,get(id,y1-1,val[id].size()))-1;
            if (pos>=(int)val[id].size()) 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 80 ms 122604 KB Output is correct
2 Correct 81 ms 122476 KB Output is correct
3 Correct 81 ms 122604 KB Output is correct
4 Correct 79 ms 122476 KB Output is correct
5 Correct 81 ms 122476 KB Output is correct
6 Correct 79 ms 122636 KB Output is correct
7 Correct 80 ms 122604 KB Output is correct
8 Correct 80 ms 122604 KB Output is correct
9 Correct 81 ms 122552 KB Output is correct
10 Correct 79 ms 122604 KB Output is correct
11 Correct 79 ms 122604 KB Output is correct
12 Correct 81 ms 122604 KB Output is correct
13 Correct 83 ms 122604 KB Output is correct
14 Correct 81 ms 122732 KB Output is correct
15 Correct 80 ms 122604 KB Output is correct
16 Correct 82 ms 123372 KB Output is correct
17 Correct 82 ms 123420 KB Output is correct
18 Correct 83 ms 123420 KB Output is correct
19 Correct 96 ms 127084 KB Output is correct
20 Correct 98 ms 127084 KB Output is correct
21 Correct 96 ms 127104 KB Output is correct
22 Correct 99 ms 126956 KB Output is correct
23 Correct 101 ms 126956 KB Output is correct
24 Correct 99 ms 126956 KB Output is correct
25 Correct 98 ms 126956 KB Output is correct
26 Correct 101 ms 126956 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1221 ms 404572 KB Output is correct
2 Correct 1211 ms 402756 KB Output is correct
3 Correct 1211 ms 403548 KB Output is correct
4 Correct 1226 ms 404824 KB Output is correct
5 Correct 1290 ms 399004 KB Output is correct
6 Correct 1755 ms 399212 KB Output is correct
7 Correct 1317 ms 399212 KB Output is correct
8 Correct 1435 ms 399160 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 122616 KB Output is correct
2 Correct 928 ms 215560 KB Output is correct
3 Execution timed out 3044 ms 402796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2928 ms 402640 KB Output is correct
2 Correct 2635 ms 401604 KB Output is correct
3 Correct 1924 ms 402528 KB Output is correct
4 Correct 2704 ms 402028 KB Output is correct
5 Correct 2678 ms 402424 KB Output is correct
6 Correct 1816 ms 402284 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 122604 KB Output is correct
2 Correct 81 ms 122476 KB Output is correct
3 Correct 81 ms 122604 KB Output is correct
4 Correct 79 ms 122476 KB Output is correct
5 Correct 81 ms 122476 KB Output is correct
6 Correct 79 ms 122636 KB Output is correct
7 Correct 80 ms 122604 KB Output is correct
8 Correct 80 ms 122604 KB Output is correct
9 Correct 81 ms 122552 KB Output is correct
10 Correct 79 ms 122604 KB Output is correct
11 Correct 79 ms 122604 KB Output is correct
12 Correct 81 ms 122604 KB Output is correct
13 Correct 83 ms 122604 KB Output is correct
14 Correct 81 ms 122732 KB Output is correct
15 Correct 80 ms 122604 KB Output is correct
16 Correct 82 ms 123372 KB Output is correct
17 Correct 82 ms 123420 KB Output is correct
18 Correct 83 ms 123420 KB Output is correct
19 Correct 96 ms 127084 KB Output is correct
20 Correct 98 ms 127084 KB Output is correct
21 Correct 96 ms 127104 KB Output is correct
22 Correct 99 ms 126956 KB Output is correct
23 Correct 101 ms 126956 KB Output is correct
24 Correct 99 ms 126956 KB Output is correct
25 Correct 98 ms 126956 KB Output is correct
26 Correct 101 ms 126956 KB Output is correct
27 Correct 122 ms 131820 KB Output is correct
28 Correct 122 ms 131820 KB Output is correct
29 Correct 123 ms 131820 KB Output is correct
30 Correct 151 ms 131692 KB Output is correct
31 Correct 139 ms 131564 KB Output is correct
32 Correct 138 ms 131568 KB Output is correct
33 Correct 613 ms 216932 KB Output is correct
34 Correct 608 ms 216804 KB Output is correct
35 Correct 618 ms 216816 KB Output is correct
36 Correct 871 ms 215404 KB Output is correct
37 Correct 879 ms 215404 KB Output is correct
38 Correct 894 ms 215532 KB Output is correct
39 Correct 960 ms 214620 KB Output is correct
40 Correct 949 ms 214684 KB Output is correct
41 Correct 932 ms 214748 KB Output is correct
42 Correct 730 ms 214316 KB Output is correct
43 Correct 766 ms 215532 KB Output is correct
44 Correct 770 ms 215324 KB Output is correct
45 Correct 756 ms 215532 KB Output is correct
46 Correct 758 ms 215276 KB Output is correct
47 Correct 770 ms 215276 KB Output is correct
48 Correct 764 ms 215404 KB Output is correct
49 Correct 757 ms 215404 KB Output is correct
50 Correct 762 ms 215500 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 122604 KB Output is correct
2 Correct 81 ms 122476 KB Output is correct
3 Correct 81 ms 122604 KB Output is correct
4 Correct 79 ms 122476 KB Output is correct
5 Correct 81 ms 122476 KB Output is correct
6 Correct 79 ms 122636 KB Output is correct
7 Correct 80 ms 122604 KB Output is correct
8 Correct 80 ms 122604 KB Output is correct
9 Correct 81 ms 122552 KB Output is correct
10 Correct 79 ms 122604 KB Output is correct
11 Correct 79 ms 122604 KB Output is correct
12 Correct 81 ms 122604 KB Output is correct
13 Correct 83 ms 122604 KB Output is correct
14 Correct 81 ms 122732 KB Output is correct
15 Correct 80 ms 122604 KB Output is correct
16 Correct 82 ms 123372 KB Output is correct
17 Correct 82 ms 123420 KB Output is correct
18 Correct 83 ms 123420 KB Output is correct
19 Correct 96 ms 127084 KB Output is correct
20 Correct 98 ms 127084 KB Output is correct
21 Correct 96 ms 127104 KB Output is correct
22 Correct 99 ms 126956 KB Output is correct
23 Correct 101 ms 126956 KB Output is correct
24 Correct 99 ms 126956 KB Output is correct
25 Correct 98 ms 126956 KB Output is correct
26 Correct 101 ms 126956 KB Output is correct
27 Correct 1221 ms 404572 KB Output is correct
28 Correct 1211 ms 402756 KB Output is correct
29 Correct 1211 ms 403548 KB Output is correct
30 Correct 1226 ms 404824 KB Output is correct
31 Correct 1290 ms 399004 KB Output is correct
32 Correct 1755 ms 399212 KB Output is correct
33 Correct 1317 ms 399212 KB Output is correct
34 Correct 1435 ms 399160 KB Output is correct
35 Correct 86 ms 122616 KB Output is correct
36 Correct 928 ms 215560 KB Output is correct
37 Execution timed out 3044 ms 402796 KB Time limit exceeded
38 Halted 0 ms 0 KB -