oj.uz

답안 #318491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318491 2020-11-02T06:36:59 Z IloveN 원 고르기 (APIO18_circle_selection) C++14
37 / 100
 3000 ms 362292 KB 
#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 it[N*4],pre[N*4],nex[N*4];
    vector<pii> val[N*4];
    pii arr[N];
    int len;

    void build_sub(int sub,int id,int l,int r)
    {
        if (l==r)
        {
            it[sub][id]=1;
            return;
        }
        int mid=(l+r)/2;
        build_sub(sub,id*2,l,mid);
        build_sub(sub,id*2+1,mid+1,r);
        it[sub][id]=1;
    }

    void build(int id,int l,int r)
    {
        if (l==r)
        {
            val[id].eb(arr[l]);
            it[id].resize(5,0);
            build_sub(id,1,1,1);
            pre[id].eb(-1);
            nex[id].eb(2);
            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());
        pre[id].resize(val[id].size());
        nex[id].resize(val[id].size());
        for (int i=0;i<(int)val[id].size();i++) pre[id][i]=i-1,nex[id][i]=i+1;
        it[id].resize(val[id].size()*4+1);
        build_sub(id,1,1,val[id].size());
    }

    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_sub(int sub,int id,int l,int r,int v)
    {
        if (l==r)
        {
            it[sub][id]=0;
            return;
        }
        int mid=(l+r)/2;
        if (v<=mid) update_sub(sub,id*2,l,mid,v);
        else update_sub(sub,id*2+1,mid+1,r,v);
        it[sub][id]=max(it[sub][id*2],it[sub][id*2+1]);
    }

    void update(int id,int l,int r,int v)
    {
        int pos=lower_bound(all(val[id]),arr[v])-val[id].begin();
        update_sub(id,1,1,val[id].size(),pos+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);
        else update(id*2+1,mid+1,r,v);
    }

    int lw_sub(int sub,int id,int l,int r,int v)
    {
        if (r<v || it[sub][id]==0) return -1;
        if (l==r) return l;
        int mid=(l+r)/2;
        int res=lw_sub(sub,id*2,l,mid,v);
        if (res==-1) return lw_sub(sub,id*2+1,mid+1,r,v);
        return res;
    }

    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()+1;
            pos=lw_sub(id,1,1,val[id].size(),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);
    }
} 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);
    read();
    process();
    return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 115424 KB Output is correct
2 Correct 76 ms 115556 KB Output is correct
3 Correct 77 ms 115428 KB Output is correct
4 Correct 75 ms 115428 KB Output is correct
5 Correct 75 ms 115428 KB Output is correct
6 Correct 76 ms 115424 KB Output is correct
7 Correct 76 ms 115428 KB Output is correct
8 Correct 77 ms 115428 KB Output is correct
9 Correct 75 ms 115428 KB Output is correct
10 Correct 77 ms 115428 KB Output is correct
11 Correct 76 ms 115428 KB Output is correct
12 Correct 77 ms 115556 KB Output is correct
13 Correct 77 ms 115432 KB Output is correct
14 Correct 77 ms 115428 KB Output is correct
15 Correct 76 ms 115428 KB Output is correct
16 Correct 79 ms 116068 KB Output is correct
17 Correct 80 ms 116068 KB Output is correct
18 Correct 78 ms 116064 KB Output is correct
19 Correct 98 ms 118884 KB Output is correct
20 Correct 96 ms 118752 KB Output is correct
21 Correct 99 ms 118756 KB Output is correct
22 Correct 101 ms 118628 KB Output is correct
23 Correct 106 ms 118628 KB Output is correct
24 Correct 103 ms 118756 KB Output is correct
25 Correct 101 ms 118628 KB Output is correct
26 Correct 101 ms 118628 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1856 ms 360824 KB Output is correct
2 Correct 1890 ms 359912 KB Output is correct
3 Correct 1888 ms 360660 KB Output is correct
4 Correct 1850 ms 361428 KB Output is correct
5 Correct 1995 ms 358116 KB Output is correct
6 Execution timed out 3044 ms 358160 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 115428 KB Output is correct
2 Correct 1552 ms 192096 KB Output is correct
3 Execution timed out 3121 ms 355684 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3053 ms 362292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 115424 KB Output is correct
2 Correct 76 ms 115556 KB Output is correct
3 Correct 77 ms 115428 KB Output is correct
4 Correct 75 ms 115428 KB Output is correct
5 Correct 75 ms 115428 KB Output is correct
6 Correct 76 ms 115424 KB Output is correct
7 Correct 76 ms 115428 KB Output is correct
8 Correct 77 ms 115428 KB Output is correct
9 Correct 75 ms 115428 KB Output is correct
10 Correct 77 ms 115428 KB Output is correct
11 Correct 76 ms 115428 KB Output is correct
12 Correct 77 ms 115556 KB Output is correct
13 Correct 77 ms 115432 KB Output is correct
14 Correct 77 ms 115428 KB Output is correct
15 Correct 76 ms 115428 KB Output is correct
16 Correct 79 ms 116068 KB Output is correct
17 Correct 80 ms 116068 KB Output is correct
18 Correct 78 ms 116064 KB Output is correct
19 Correct 98 ms 118884 KB Output is correct
20 Correct 96 ms 118752 KB Output is correct
21 Correct 99 ms 118756 KB Output is correct
22 Correct 101 ms 118628 KB Output is correct
23 Correct 106 ms 118628 KB Output is correct
24 Correct 103 ms 118756 KB Output is correct
25 Correct 101 ms 118628 KB Output is correct
26 Correct 101 ms 118628 KB Output is correct
27 Correct 124 ms 122616 KB Output is correct
28 Correct 122 ms 122468 KB Output is correct
29 Correct 123 ms 122468 KB Output is correct
30 Correct 147 ms 122340 KB Output is correct
31 Correct 142 ms 122212 KB Output is correct
32 Correct 143 ms 122212 KB Output is correct
33 Correct 866 ms 192728 KB Output is correct
34 Correct 872 ms 192732 KB Output is correct
35 Correct 876 ms 192732 KB Output is correct
36 Correct 1464 ms 191844 KB Output is correct
37 Correct 1461 ms 191716 KB Output is correct
38 Correct 1500 ms 191972 KB Output is correct
39 Correct 1411 ms 192600 KB Output is correct
40 Correct 1390 ms 192596 KB Output is correct
41 Correct 1395 ms 192612 KB Output is correct
42 Correct 1102 ms 191720 KB Output is correct
43 Correct 1299 ms 192100 KB Output is correct
44 Correct 1310 ms 191844 KB Output is correct
45 Correct 1328 ms 191844 KB Output is correct
46 Correct 1302 ms 191716 KB Output is correct
47 Correct 1301 ms 191844 KB Output is correct
48 Correct 1293 ms 191712 KB Output is correct
49 Correct 1315 ms 191716 KB Output is correct
50 Correct 1294 ms 191716 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 115424 KB Output is correct
2 Correct 76 ms 115556 KB Output is correct
3 Correct 77 ms 115428 KB Output is correct
4 Correct 75 ms 115428 KB Output is correct
5 Correct 75 ms 115428 KB Output is correct
6 Correct 76 ms 115424 KB Output is correct
7 Correct 76 ms 115428 KB Output is correct
8 Correct 77 ms 115428 KB Output is correct
9 Correct 75 ms 115428 KB Output is correct
10 Correct 77 ms 115428 KB Output is correct
11 Correct 76 ms 115428 KB Output is correct
12 Correct 77 ms 115556 KB Output is correct
13 Correct 77 ms 115432 KB Output is correct
14 Correct 77 ms 115428 KB Output is correct
15 Correct 76 ms 115428 KB Output is correct
16 Correct 79 ms 116068 KB Output is correct
17 Correct 80 ms 116068 KB Output is correct
18 Correct 78 ms 116064 KB Output is correct
19 Correct 98 ms 118884 KB Output is correct
20 Correct 96 ms 118752 KB Output is correct
21 Correct 99 ms 118756 KB Output is correct
22 Correct 101 ms 118628 KB Output is correct
23 Correct 106 ms 118628 KB Output is correct
24 Correct 103 ms 118756 KB Output is correct
25 Correct 101 ms 118628 KB Output is correct
26 Correct 101 ms 118628 KB Output is correct
27 Correct 1856 ms 360824 KB Output is correct
28 Correct 1890 ms 359912 KB Output is correct
29 Correct 1888 ms 360660 KB Output is correct
30 Correct 1850 ms 361428 KB Output is correct
31 Correct 1995 ms 358116 KB Output is correct
32 Execution timed out 3044 ms 358160 KB Time limit exceeded
33 Halted 0 ms 0 KB -