oj.uz

답안 #354542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
354542 2021-01-22T03:51:10 Z IloveN 원 고르기 (APIO18_circle_selection) C++14
72 / 100
 3000 ms 397924 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,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

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 122560 KB Output is correct
2 Correct 96 ms 122604 KB Output is correct
3 Correct 86 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 87 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 86 ms 122568 KB Output is correct
12 Correct 86 ms 122732 KB Output is correct
13 Correct 86 ms 122604 KB Output is correct
14 Correct 88 ms 122604 KB Output is correct
15 Correct 89 ms 122732 KB Output is correct
16 Correct 89 ms 123500 KB Output is correct
17 Correct 89 ms 123372 KB Output is correct
18 Correct 89 ms 123372 KB Output is correct
19 Correct 104 ms 126956 KB Output is correct
20 Correct 102 ms 127068 KB Output is correct
21 Correct 103 ms 127084 KB Output is correct
22 Correct 105 ms 126828 KB Output is correct
23 Correct 107 ms 126956 KB Output is correct
24 Correct 105 ms 126828 KB Output is correct
25 Correct 105 ms 126828 KB Output is correct
26 Correct 107 ms 126920 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1229 ms 397924 KB Output is correct
2 Correct 1210 ms 396156 KB Output is correct
3 Correct 1220 ms 396764 KB Output is correct
4 Correct 1188 ms 397916 KB Output is correct
5 Correct 1273 ms 394476 KB Output is correct
6 Correct 1745 ms 394476 KB Output is correct
7 Correct 1335 ms 394476 KB Output is correct
8 Correct 1460 ms 394348 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 122604 KB Output is correct
2 Correct 947 ms 212716 KB Output is correct
3 Execution timed out 3056 ms 394356 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2993 ms 394572 KB Output is correct
2 Correct 2644 ms 395036 KB Output is correct
3 Correct 1936 ms 394220 KB Output is correct
4 Correct 2693 ms 394820 KB Output is correct
5 Correct 2697 ms 394944 KB Output is correct
6 Correct 1777 ms 394220 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 122560 KB Output is correct
2 Correct 96 ms 122604 KB Output is correct
3 Correct 86 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 87 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 86 ms 122568 KB Output is correct
12 Correct 86 ms 122732 KB Output is correct
13 Correct 86 ms 122604 KB Output is correct
14 Correct 88 ms 122604 KB Output is correct
15 Correct 89 ms 122732 KB Output is correct
16 Correct 89 ms 123500 KB Output is correct
17 Correct 89 ms 123372 KB Output is correct
18 Correct 89 ms 123372 KB Output is correct
19 Correct 104 ms 126956 KB Output is correct
20 Correct 102 ms 127068 KB Output is correct
21 Correct 103 ms 127084 KB Output is correct
22 Correct 105 ms 126828 KB Output is correct
23 Correct 107 ms 126956 KB Output is correct
24 Correct 105 ms 126828 KB Output is correct
25 Correct 105 ms 126828 KB Output is correct
26 Correct 107 ms 126920 KB Output is correct
27 Correct 121 ms 131436 KB Output is correct
28 Correct 125 ms 131436 KB Output is correct
29 Correct 126 ms 131436 KB Output is correct
30 Correct 137 ms 131288 KB Output is correct
31 Correct 133 ms 131308 KB Output is correct
32 Correct 136 ms 131308 KB Output is correct
33 Correct 615 ms 213732 KB Output is correct
34 Correct 609 ms 213732 KB Output is correct
35 Correct 625 ms 213860 KB Output is correct
36 Correct 886 ms 212972 KB Output is correct
37 Correct 868 ms 212716 KB Output is correct
38 Correct 883 ms 212832 KB Output is correct
39 Correct 949 ms 213468 KB Output is correct
40 Correct 948 ms 213512 KB Output is correct
41 Correct 942 ms 213596 KB Output is correct
42 Correct 741 ms 212588 KB Output is correct
43 Correct 756 ms 212776 KB Output is correct
44 Correct 764 ms 212716 KB Output is correct
45 Correct 769 ms 212780 KB Output is correct
46 Correct 772 ms 212920 KB Output is correct
47 Correct 768 ms 212716 KB Output is correct
48 Correct 756 ms 212716 KB Output is correct
49 Correct 781 ms 212700 KB Output is correct
50 Correct 762 ms 212844 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 122560 KB Output is correct
2 Correct 96 ms 122604 KB Output is correct
3 Correct 86 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 87 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 86 ms 122568 KB Output is correct
12 Correct 86 ms 122732 KB Output is correct
13 Correct 86 ms 122604 KB Output is correct
14 Correct 88 ms 122604 KB Output is correct
15 Correct 89 ms 122732 KB Output is correct
16 Correct 89 ms 123500 KB Output is correct
17 Correct 89 ms 123372 KB Output is correct
18 Correct 89 ms 123372 KB Output is correct
19 Correct 104 ms 126956 KB Output is correct
20 Correct 102 ms 127068 KB Output is correct
21 Correct 103 ms 127084 KB Output is correct
22 Correct 105 ms 126828 KB Output is correct
23 Correct 107 ms 126956 KB Output is correct
24 Correct 105 ms 126828 KB Output is correct
25 Correct 105 ms 126828 KB Output is correct
26 Correct 107 ms 126920 KB Output is correct
27 Correct 1229 ms 397924 KB Output is correct
28 Correct 1210 ms 396156 KB Output is correct
29 Correct 1220 ms 396764 KB Output is correct
30 Correct 1188 ms 397916 KB Output is correct
31 Correct 1273 ms 394476 KB Output is correct
32 Correct 1745 ms 394476 KB Output is correct
33 Correct 1335 ms 394476 KB Output is correct
34 Correct 1460 ms 394348 KB Output is correct
35 Correct 87 ms 122604 KB Output is correct
36 Correct 947 ms 212716 KB Output is correct
37 Execution timed out 3056 ms 394356 KB Time limit exceeded
38 Halted 0 ms 0 KB -