oj.uz

Submission #710119

# Submission time Handle Problem Language Result Execution time Memory
710119 2023-03-15T04:53:16 Z lam Circle selection (APIO18_circle_selection) C++17
7 / 100
 3000 ms 554496 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define ll 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 ll calc(ii x, ii y)
{
    return 1LL*(x.ff-y.ff)*(x.ff-y.ff) + 1LL*(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])
            {
                ll val = calc(a[v].ff,a[idx].ff);
                ll val2 = 1LL*(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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 112972 KB Output is correct
2 Correct 53 ms 113052 KB Output is correct
3 Correct 53 ms 113052 KB Output is correct
4 Correct 66 ms 112992 KB Output is correct
5 Correct 63 ms 113056 KB Output is correct
6 Correct 51 ms 113236 KB Output is correct
7 Correct 58 ms 113132 KB Output is correct
8 Correct 50 ms 113144 KB Output is correct
9 Correct 52 ms 113228 KB Output is correct
10 Correct 57 ms 113148 KB Output is correct
11 Correct 60 ms 113124 KB Output is correct
12 Correct 54 ms 113132 KB Output is correct
13 Correct 51 ms 113228 KB Output is correct
14 Correct 53 ms 113232 KB Output is correct
15 Correct 52 ms 113172 KB Output is correct
16 Correct 66 ms 115440 KB Output is correct
17 Correct 77 ms 115444 KB Output is correct
18 Correct 64 ms 115400 KB Output is correct
19 Correct 154 ms 127192 KB Output is correct
20 Correct 136 ms 127244 KB Output is correct
21 Correct 185 ms 127296 KB Output is correct
22 Correct 164 ms 127264 KB Output is correct
23 Correct 184 ms 127152 KB Output is correct
24 Correct 147 ms 127180 KB Output is correct
25 Correct 151 ms 127148 KB Output is correct
26 Correct 161 ms 127184 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 401092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 113024 KB Output is correct
2 Execution timed out 3113 ms 477120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 554496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 112972 KB Output is correct
2 Correct 53 ms 113052 KB Output is correct
3 Correct 53 ms 113052 KB Output is correct
4 Correct 66 ms 112992 KB Output is correct
5 Correct 63 ms 113056 KB Output is correct
6 Correct 51 ms 113236 KB Output is correct
7 Correct 58 ms 113132 KB Output is correct
8 Correct 50 ms 113144 KB Output is correct
9 Correct 52 ms 113228 KB Output is correct
10 Correct 57 ms 113148 KB Output is correct
11 Correct 60 ms 113124 KB Output is correct
12 Correct 54 ms 113132 KB Output is correct
13 Correct 51 ms 113228 KB Output is correct
14 Correct 53 ms 113232 KB Output is correct
15 Correct 52 ms 113172 KB Output is correct
16 Correct 66 ms 115440 KB Output is correct
17 Correct 77 ms 115444 KB Output is correct
18 Correct 64 ms 115400 KB Output is correct
19 Correct 154 ms 127192 KB Output is correct
20 Correct 136 ms 127244 KB Output is correct
21 Correct 185 ms 127296 KB Output is correct
22 Correct 164 ms 127264 KB Output is correct
23 Correct 184 ms 127152 KB Output is correct
24 Correct 147 ms 127180 KB Output is correct
25 Correct 151 ms 127148 KB Output is correct
26 Correct 161 ms 127184 KB Output is correct
27 Correct 404 ms 143372 KB Output is correct
28 Correct 356 ms 143316 KB Output is correct
29 Correct 434 ms 143352 KB Output is correct
30 Correct 344 ms 143200 KB Output is correct
31 Correct 346 ms 143200 KB Output is correct
32 Correct 332 ms 143208 KB Output is correct
33 Execution timed out 3093 ms 377504 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 112972 KB Output is correct
2 Correct 53 ms 113052 KB Output is correct
3 Correct 53 ms 113052 KB Output is correct
4 Correct 66 ms 112992 KB Output is correct
5 Correct 63 ms 113056 KB Output is correct
6 Correct 51 ms 113236 KB Output is correct
7 Correct 58 ms 113132 KB Output is correct
8 Correct 50 ms 113144 KB Output is correct
9 Correct 52 ms 113228 KB Output is correct
10 Correct 57 ms 113148 KB Output is correct
11 Correct 60 ms 113124 KB Output is correct
12 Correct 54 ms 113132 KB Output is correct
13 Correct 51 ms 113228 KB Output is correct
14 Correct 53 ms 113232 KB Output is correct
15 Correct 52 ms 113172 KB Output is correct
16 Correct 66 ms 115440 KB Output is correct
17 Correct 77 ms 115444 KB Output is correct
18 Correct 64 ms 115400 KB Output is correct
19 Correct 154 ms 127192 KB Output is correct
20 Correct 136 ms 127244 KB Output is correct
21 Correct 185 ms 127296 KB Output is correct
22 Correct 164 ms 127264 KB Output is correct
23 Correct 184 ms 127152 KB Output is correct
24 Correct 147 ms 127180 KB Output is correct
25 Correct 151 ms 127148 KB Output is correct
26 Correct 161 ms 127184 KB Output is correct
27 Execution timed out 3075 ms 401092 KB Time limit exceeded
28 Halted 0 ms 0 KB -