oj.uz

Submission #354540

# Submission time Handle Problem Language Result Execution time Memory
354540 2021-01-22T03:46:20 Z IloveN Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 398372 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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;
}

Compilation message

circle_selection.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
circle_selection.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 122476 KB Output is correct
2 Correct 86 ms 122476 KB Output is correct
3 Correct 87 ms 122476 KB Output is correct
4 Correct 87 ms 122604 KB Output is correct
5 Correct 88 ms 122604 KB Output is correct
6 Correct 90 ms 122604 KB Output is correct
7 Correct 88 ms 122604 KB Output is correct
8 Correct 88 ms 122604 KB Output is correct
9 Correct 90 ms 122604 KB Output is correct
10 Correct 87 ms 122604 KB Output is correct
11 Correct 86 ms 122604 KB Output is correct
12 Correct 87 ms 122604 KB Output is correct
13 Correct 87 ms 122604 KB Output is correct
14 Correct 89 ms 122604 KB Output is correct
15 Correct 89 ms 122604 KB Output is correct
16 Correct 101 ms 123372 KB Output is correct
17 Correct 97 ms 123500 KB Output is correct
18 Correct 90 ms 123372 KB Output is correct
19 Correct 106 ms 127084 KB Output is correct
20 Correct 107 ms 127084 KB Output is correct
21 Correct 104 ms 126956 KB Output is correct
22 Correct 106 ms 126956 KB Output is correct
23 Correct 108 ms 126956 KB Output is correct
24 Correct 107 ms 126956 KB Output is correct
25 Correct 106 ms 126956 KB Output is correct
26 Correct 106 ms 126956 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1216 ms 398340 KB Output is correct
2 Correct 1233 ms 396772 KB Output is correct
3 Correct 1217 ms 397404 KB Output is correct
4 Correct 1208 ms 398372 KB Output is correct
5 Correct 1278 ms 395248 KB Output is correct
6 Correct 1754 ms 395116 KB Output is correct
7 Correct 1330 ms 395136 KB Output is correct
8 Correct 1450 ms 394956 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 122476 KB Output is correct
2 Correct 954 ms 213288 KB Output is correct
3 Execution timed out 3090 ms 395116 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 3007 ms 395204 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 122476 KB Output is correct
2 Correct 86 ms 122476 KB Output is correct
3 Correct 87 ms 122476 KB Output is correct
4 Correct 87 ms 122604 KB Output is correct
5 Correct 88 ms 122604 KB Output is correct
6 Correct 90 ms 122604 KB Output is correct
7 Correct 88 ms 122604 KB Output is correct
8 Correct 88 ms 122604 KB Output is correct
9 Correct 90 ms 122604 KB Output is correct
10 Correct 87 ms 122604 KB Output is correct
11 Correct 86 ms 122604 KB Output is correct
12 Correct 87 ms 122604 KB Output is correct
13 Correct 87 ms 122604 KB Output is correct
14 Correct 89 ms 122604 KB Output is correct
15 Correct 89 ms 122604 KB Output is correct
16 Correct 101 ms 123372 KB Output is correct
17 Correct 97 ms 123500 KB Output is correct
18 Correct 90 ms 123372 KB Output is correct
19 Correct 106 ms 127084 KB Output is correct
20 Correct 107 ms 127084 KB Output is correct
21 Correct 104 ms 126956 KB Output is correct
22 Correct 106 ms 126956 KB Output is correct
23 Correct 108 ms 126956 KB Output is correct
24 Correct 107 ms 126956 KB Output is correct
25 Correct 106 ms 126956 KB Output is correct
26 Correct 106 ms 126956 KB Output is correct
27 Correct 128 ms 131692 KB Output is correct
28 Correct 125 ms 131688 KB Output is correct
29 Correct 125 ms 131728 KB Output is correct
30 Correct 147 ms 131588 KB Output is correct
31 Correct 134 ms 131564 KB Output is correct
32 Correct 135 ms 131564 KB Output is correct
33 Correct 627 ms 213996 KB Output is correct
34 Correct 638 ms 213988 KB Output is correct
35 Correct 642 ms 213988 KB Output is correct
36 Correct 892 ms 212972 KB Output is correct
37 Correct 897 ms 212972 KB Output is correct
38 Correct 906 ms 213048 KB Output is correct
39 Correct 944 ms 213760 KB Output is correct
40 Correct 960 ms 213872 KB Output is correct
41 Correct 960 ms 213852 KB Output is correct
42 Correct 757 ms 212920 KB Output is correct
43 Correct 780 ms 212956 KB Output is correct
44 Correct 759 ms 212972 KB Output is correct
45 Correct 777 ms 213100 KB Output is correct
46 Correct 785 ms 213100 KB Output is correct
47 Correct 769 ms 213100 KB Output is correct
48 Correct 763 ms 213100 KB Output is correct
49 Correct 783 ms 212972 KB Output is correct
50 Correct 767 ms 213228 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 122476 KB Output is correct
2 Correct 86 ms 122476 KB Output is correct
3 Correct 87 ms 122476 KB Output is correct
4 Correct 87 ms 122604 KB Output is correct
5 Correct 88 ms 122604 KB Output is correct
6 Correct 90 ms 122604 KB Output is correct
7 Correct 88 ms 122604 KB Output is correct
8 Correct 88 ms 122604 KB Output is correct
9 Correct 90 ms 122604 KB Output is correct
10 Correct 87 ms 122604 KB Output is correct
11 Correct 86 ms 122604 KB Output is correct
12 Correct 87 ms 122604 KB Output is correct
13 Correct 87 ms 122604 KB Output is correct
14 Correct 89 ms 122604 KB Output is correct
15 Correct 89 ms 122604 KB Output is correct
16 Correct 101 ms 123372 KB Output is correct
17 Correct 97 ms 123500 KB Output is correct
18 Correct 90 ms 123372 KB Output is correct
19 Correct 106 ms 127084 KB Output is correct
20 Correct 107 ms 127084 KB Output is correct
21 Correct 104 ms 126956 KB Output is correct
22 Correct 106 ms 126956 KB Output is correct
23 Correct 108 ms 126956 KB Output is correct
24 Correct 107 ms 126956 KB Output is correct
25 Correct 106 ms 126956 KB Output is correct
26 Correct 106 ms 126956 KB Output is correct
27 Correct 1216 ms 398340 KB Output is correct
28 Correct 1233 ms 396772 KB Output is correct
29 Correct 1217 ms 397404 KB Output is correct
30 Correct 1208 ms 398372 KB Output is correct
31 Correct 1278 ms 395248 KB Output is correct
32 Correct 1754 ms 395116 KB Output is correct
33 Correct 1330 ms 395136 KB Output is correct
34 Correct 1450 ms 394956 KB Output is correct
35 Correct 88 ms 122476 KB Output is correct
36 Correct 954 ms 213288 KB Output is correct
37 Execution timed out 3090 ms 395116 KB Time limit exceeded
38 Halted 0 ms 0 KB -