Submission #710105

#	Time	Username	Problem	Language	Result	Execution time	Memory
710105		lam	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3118 ms	615160 KiB

circle_selection

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define int long long
using namespace std;
const int maxn = 3e5 + 10;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ii,ii> iiii;
#define ff first
#define ss second
inline int calc(ii x, ii y)
{
    return (x.ff-y.ff)*(x.ff-y.ff) + (x.ss-y.ss)*(x.ss-y.ss);
}
bool dau[maxn];
int res[maxn];
int n,m;
iii a[maxn];
int id[maxn];
iiii hcn[maxn];
multiset<ii> f[8*maxn];
vector <int> tmp;
bool cmp(int x, int y)
{
    if (a[x].ss!=a[y].ss) return a[x].ss>a[y].ss;
    return x<y;
}
void update(int x, int lx, int rx, int idx, ii val)
{
//    if (x==1)
//    {
////        cout<<"+ "<<idx<<' '<<val.ff<<','<<val.ss<<'\n';
//    }
    f[x].insert(val);
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (idx<=mid) update(2*x,lx,mid,idx,val);
    else update(2*x+1,mid+1,rx,idx,val);
}
void xoa(int x, int lx, int rx, int idx, ii val)
{
    f[x].erase(f[x].find(val));
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (idx<=mid) xoa(2*x,lx,mid,idx,val);
    else xoa(2*x+1,mid+1,rx,idx,val);
}
void qry(int x, int lx, int rx, int l, int r, int l2, int r2, int idx)
{
    if (lx>r||rx<l) return;
    if (lx>=l&&rx<=r)
    {
        ii temp = {l2,-1};
        auto j = f[x].lower_bound(temp);
        while (j!=f[x].end()&&(*j).ff <= r2)
        {
//            cerr<<l2<<" :: "<<r2<<" == "<<(*j).ff<<" , "<<(*j).ss<<endl;
            int v = (*j).ss; j++;
            if (!dau[v])
            {
                int val = calc(a[v].ff,a[idx].ff);
                int val2 = (a[v].ss+a[idx].ss); val2*=val2;
                if (val>val2) continue;
                dau[v] = 1;
                tmp.push_back(v);
            }
        }
        return;
    }
    int mid=(lx+rx)/2;
    qry(2*x,lx,mid,l,r,l2,r2,idx);
    qry(2*x+1,mid+1,rx,l,r,l2,r2,idx);
}
signed main()

{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n;
    map<int,int> mp;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i].ff.ff>>a[i].ff.ss>>a[i].ss;
        hcn[i] = {{a[i].ff.ff-a[i].ss,a[i].ff.ss-a[i].ss},{a[i].ff.ff+a[i].ss,a[i].ff.ss + a[i].ss}};
        mp[hcn[i].ff.ff] = 1;
        mp[hcn[i].ss.ff] = 1;
        dau[i]=0;
        id[i]=i;
    }
    m=0;
    for (auto &c:mp) c.ss = ++m;
    for (int i=1; i<=n; i++)
    {
        hcn[i].ff.ff = mp[hcn[i].ff.ff];
        hcn[i].ss.ff = mp[hcn[i].ss.ff];
//        cerr<<i<<" := "<<hcn[i].ff.ff<<" - "<<hcn[i].ss.ff<<" : "<<hcn[i].ff.ss<<' '<<hcn[i].ss.ss<<endl;
        update(1,1,m,hcn[i].ff.ff,{hcn[i].ff.ss,i});
        update(1,1,m,hcn[i].ff.ff,{hcn[i].ss.ss,i});
        update(1,1,m,hcn[i].ss.ff,{hcn[i].ff.ss,i});
        update(1,1,m,hcn[i].ss.ff,{hcn[i].ss.ss,i});
    }
    sort(id+1,id+n+1,cmp);
    for (int i=1; i<=n; i++)
    {
        int j=id[i];
        if (dau[j]) continue;
        tmp.clear();
        qry(1,1,m,hcn[j].ff.ff,hcn[j].ss.ff,hcn[j].ff.ss,hcn[j].ss.ss,j);
//        cerr<<j<<" !!"<<endl;
        for (int u:tmp)
        {
//            cerr<<u<<endl;
            res[u] = j;
            xoa(1,1,m,hcn[u].ff.ff,{hcn[u].ff.ss,u});
            xoa(1,1,m,hcn[u].ff.ff,{hcn[u].ss.ss,u});
            xoa(1,1,m,hcn[u].ss.ff,{hcn[u].ff.ss,u});
            xoa(1,1,m,hcn[u].ss.ff,{hcn[u].ss.ss,u});
        }
    }
    for (int i=1; i<=n; i++) cout<<res[i]<<' '; cout<<'\n';
}
/**
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
**/

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:121:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  121 |     for (int i=1; i<=n; i++) cout<<res[i]<<' '; cout<<'\n';
      |     ^~~
circle_selection.cpp:121:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  121 |     for (int i=1; i<=n; i++) cout<<res[i]<<' '; cout<<'\n';
      |                                                 ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13