oj.uz

Submission #354543

# Submission time Handle Problem Language Result Execution time Memory
354543 2021-01-22T03:52:50 Z IloveN Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 397788 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,fma")
#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 98 ms 122476 KB Output is correct
2 Correct 88 ms 122536 KB Output is correct
3 Correct 88 ms 122604 KB Output is correct
4 Correct 86 ms 122476 KB Output is correct
5 Correct 88 ms 122476 KB Output is correct
6 Correct 86 ms 122604 KB Output is correct
7 Correct 87 ms 122604 KB Output is correct
8 Correct 87 ms 122604 KB Output is correct
9 Correct 86 ms 122604 KB Output is correct
10 Correct 86 ms 122604 KB Output is correct
11 Correct 87 ms 122604 KB Output is correct
12 Correct 92 ms 122604 KB Output is correct
13 Correct 87 ms 122604 KB Output is correct
14 Correct 100 ms 122604 KB Output is correct
15 Correct 87 ms 122604 KB Output is correct
16 Correct 91 ms 123500 KB Output is correct
17 Correct 90 ms 123372 KB Output is correct
18 Correct 89 ms 123372 KB Output is correct
19 Correct 123 ms 127104 KB Output is correct
20 Correct 104 ms 126896 KB Output is correct
21 Correct 117 ms 126956 KB Output is correct
22 Correct 107 ms 126828 KB Output is correct
23 Correct 107 ms 126956 KB Output is correct
24 Correct 107 ms 126828 KB Output is correct
25 Correct 106 ms 126828 KB Output is correct
26 Correct 106 ms 126828 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 397744 KB Output is correct
2 Correct 1220 ms 395972 KB Output is correct
3 Correct 1211 ms 396848 KB Output is correct
4 Correct 1211 ms 397788 KB Output is correct
5 Correct 1290 ms 394476 KB Output is correct
6 Correct 1751 ms 394340 KB Output is correct
7 Correct 1337 ms 394444 KB Output is correct
8 Correct 1439 ms 394340 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 122476 KB Output is correct
2 Correct 950 ms 212848 KB Output is correct
3 Execution timed out 3071 ms 394348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2968 ms 394340 KB Output is correct
2 Correct 2719 ms 394364 KB Output is correct
3 Correct 1955 ms 393980 KB Output is correct
4 Correct 2722 ms 394628 KB Output is correct
5 Correct 2674 ms 394348 KB Output is correct
6 Correct 1813 ms 393708 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 122476 KB Output is correct
2 Correct 88 ms 122536 KB Output is correct
3 Correct 88 ms 122604 KB Output is correct
4 Correct 86 ms 122476 KB Output is correct
5 Correct 88 ms 122476 KB Output is correct
6 Correct 86 ms 122604 KB Output is correct
7 Correct 87 ms 122604 KB Output is correct
8 Correct 87 ms 122604 KB Output is correct
9 Correct 86 ms 122604 KB Output is correct
10 Correct 86 ms 122604 KB Output is correct
11 Correct 87 ms 122604 KB Output is correct
12 Correct 92 ms 122604 KB Output is correct
13 Correct 87 ms 122604 KB Output is correct
14 Correct 100 ms 122604 KB Output is correct
15 Correct 87 ms 122604 KB Output is correct
16 Correct 91 ms 123500 KB Output is correct
17 Correct 90 ms 123372 KB Output is correct
18 Correct 89 ms 123372 KB Output is correct
19 Correct 123 ms 127104 KB Output is correct
20 Correct 104 ms 126896 KB Output is correct
21 Correct 117 ms 126956 KB Output is correct
22 Correct 107 ms 126828 KB Output is correct
23 Correct 107 ms 126956 KB Output is correct
24 Correct 107 ms 126828 KB Output is correct
25 Correct 106 ms 126828 KB Output is correct
26 Correct 106 ms 126828 KB Output is correct
27 Correct 124 ms 131436 KB Output is correct
28 Correct 123 ms 131436 KB Output is correct
29 Correct 123 ms 131436 KB Output is correct
30 Correct 135 ms 131308 KB Output is correct
31 Correct 135 ms 131308 KB Output is correct
32 Correct 135 ms 131308 KB Output is correct
33 Correct 632 ms 213732 KB Output is correct
34 Correct 627 ms 213732 KB Output is correct
35 Correct 628 ms 213860 KB Output is correct
36 Correct 872 ms 212692 KB Output is correct
37 Correct 877 ms 212844 KB Output is correct
38 Correct 890 ms 212972 KB Output is correct
39 Correct 937 ms 213452 KB Output is correct
40 Correct 984 ms 213596 KB Output is correct
41 Correct 942 ms 213596 KB Output is correct
42 Correct 748 ms 212588 KB Output is correct
43 Correct 766 ms 212844 KB Output is correct
44 Correct 772 ms 212844 KB Output is correct
45 Correct 765 ms 212844 KB Output is correct
46 Correct 770 ms 213016 KB Output is correct
47 Correct 769 ms 212716 KB Output is correct
48 Correct 786 ms 212716 KB Output is correct
49 Correct 766 ms 212716 KB Output is correct
50 Correct 767 ms 212844 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 122476 KB Output is correct
2 Correct 88 ms 122536 KB Output is correct
3 Correct 88 ms 122604 KB Output is correct
4 Correct 86 ms 122476 KB Output is correct
5 Correct 88 ms 122476 KB Output is correct
6 Correct 86 ms 122604 KB Output is correct
7 Correct 87 ms 122604 KB Output is correct
8 Correct 87 ms 122604 KB Output is correct
9 Correct 86 ms 122604 KB Output is correct
10 Correct 86 ms 122604 KB Output is correct
11 Correct 87 ms 122604 KB Output is correct
12 Correct 92 ms 122604 KB Output is correct
13 Correct 87 ms 122604 KB Output is correct
14 Correct 100 ms 122604 KB Output is correct
15 Correct 87 ms 122604 KB Output is correct
16 Correct 91 ms 123500 KB Output is correct
17 Correct 90 ms 123372 KB Output is correct
18 Correct 89 ms 123372 KB Output is correct
19 Correct 123 ms 127104 KB Output is correct
20 Correct 104 ms 126896 KB Output is correct
21 Correct 117 ms 126956 KB Output is correct
22 Correct 107 ms 126828 KB Output is correct
23 Correct 107 ms 126956 KB Output is correct
24 Correct 107 ms 126828 KB Output is correct
25 Correct 106 ms 126828 KB Output is correct
26 Correct 106 ms 126828 KB Output is correct
27 Correct 1200 ms 397744 KB Output is correct
28 Correct 1220 ms 395972 KB Output is correct
29 Correct 1211 ms 396848 KB Output is correct
30 Correct 1211 ms 397788 KB Output is correct
31 Correct 1290 ms 394476 KB Output is correct
32 Correct 1751 ms 394340 KB Output is correct
33 Correct 1337 ms 394444 KB Output is correct
34 Correct 1439 ms 394340 KB Output is correct
35 Correct 86 ms 122476 KB Output is correct
36 Correct 950 ms 212848 KB Output is correct
37 Execution timed out 3071 ms 394348 KB Time limit exceeded
38 Halted 0 ms 0 KB -