oj.uz

Submission #772050

# Submission time Handle Problem Language Result Execution time Memory
772050 2023-07-03T14:50:16 Z bgnbvnbv Park (BOI16_park) C++14
100 / 100
 789 ms 1860 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e4;
const ll inf=1e18;
const ll mod=1e9+7;
ll w,h;

// y la doc
// x la ngang
ll mnx[maxN],mny[maxN],mxx[maxN],mxy[maxN];
bool check(ll i,ll j,ll id,ll bk)
{
    i++,j++;
    if(i==1&&j==2)
    {
        if(mny[id]<=bk&&mxy[id]>=h-bk) return false;
        if((mny[id]<=bk&&mnx[id]<=bk)||(mny[id]<=bk&&mxx[id]>=w-bk)) return false;
    }
    else if(i==1&&j==3)
    {
        if((mny[id]<=bk&&mxy[id]>=h-bk)||(mnx[id]<=bk&&mxx[id]>=w-bk)) return false;
        if((mny[id]<=bk&&mnx[id]<=bk)||(mxx[id]>=w-bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==1&&j==4)
    {
        if(mnx[id]<=bk&&mxx[id]>=w-bk) return false;
        if((mny[id]<=bk&&mnx[id]<=bk)||(mnx[id]<=bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==2&&j==3)
    {
        if(mnx[id]<=bk&&mxx[id]>=w-bk) return false;
        if((mny[id]<=bk&&mxx[id]>=w-bk)||(mxx[id]>=w-bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==2&&j==4)
    {
        if((mny[id]<=bk&&mxy[id]>=h-bk)||(mnx[id]<=bk&&mxx[id]>=w-bk)) return false;
        if((mny[id]<=bk&&mxx[id]>=w-bk)||(mnx[id]<=bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==3&&j==4)
    {
        if(mny[id]<=bk&&mxy[id]>=h-bk) return false;
        if((mxx[id]>=w-bk&&mxy[id]>=h-bk)||(mnx[id]<=bk&&mxy[id]>=h-bk)) return false ;
    }
    return true;
}
ll n,m;
ll x[maxN],y[maxN],r[maxN];
ll lim[5][5];
ll lab[maxN];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return;
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
    mnx[u]=min(mnx[u],mnx[v]);
    mny[u]=min(mny[u],mny[v]);
    mxx[u]=max(mxx[u],mxx[v]);
    mxy[u]=max(mxy[u],mxy[v]);
}
ll dis(ll i,ll j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}

bool chk(ll q,ll k,ll mid)
{
    for(int i=1;i<=n;i++)
    {
        lab[i]=-1;
        mnx[i]=x[i]-r[i]-mid;
        mxx[i]=x[i]+r[i]+mid;
        mny[i]=y[i]-r[i]-mid;
        mxy[i]=y[i]+r[i]+mid;
        for(int j=1;j<i;j++)
        {
            if(dis(i,j)<(r[i]+r[j]+2*mid)*(r[i]+r[j]+2*mid)) unite(i,j);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(findset(i)==i)
        {
            if(check(q,k,i,mid)==false) return false;
        }
    }
    return true;
}
void solve()
{
    cin >> n >> m;
    cin >> w >> h;
    for(int i=1;i<=n;i++)
    {
        cin >> x[i] >> y[i] >> r[i];
    }
    for(int q=0;q<4;q++)
    {
        for(int k=q+1;k<4;k++)
        {
            ll low=0,high=min(w,h)/4;
            while(low<=high)
            {
                ll mid=low+high>>1;
                if(chk(q,k,mid)) low=mid+1;
                else high=mid-1;
            }
            lim[q][k]=high;
        }
    }
    for(int i=1;i<=m;i++)
    {
        ll id,ra;
        cin >> ra >> id;
        id--;
        for(int j=0;j<id;j++)
        {
            //cout << j<<' '<<lim[j][id]<<'\n';
            if(lim[j][id]>=ra) cout << j+1;
        }
        cout << id+1;
        for(int j=id+1;j<4;j++)
        {
            //cout << j<<' '<<lim[id][j]<<'\n';
            if(lim[id][j]>=ra) cout << j+1;
        }
        cout << '\n';
    }
    //cout << lim[0][2];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

park.cpp: In function 'void solve()':
park.cpp:117:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |                 ll mid=low+high>>1;
      |                        ~~~^~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 524 KB Output is correct
2 Correct 454 ms 520 KB Output is correct
3 Correct 414 ms 520 KB Output is correct
4 Correct 429 ms 468 KB Output is correct
5 Correct 458 ms 468 KB Output is correct
6 Correct 408 ms 468 KB Output is correct
7 Correct 737 ms 516 KB Output is correct
8 Correct 759 ms 520 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1720 KB Output is correct
2 Correct 32 ms 1632 KB Output is correct
3 Correct 29 ms 1700 KB Output is correct
4 Correct 28 ms 1700 KB Output is correct
5 Correct 32 ms 1732 KB Output is correct
6 Correct 43 ms 1708 KB Output is correct
7 Correct 29 ms 1792 KB Output is correct
8 Correct 23 ms 1824 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 524 KB Output is correct
2 Correct 454 ms 520 KB Output is correct
3 Correct 414 ms 520 KB Output is correct
4 Correct 429 ms 468 KB Output is correct
5 Correct 458 ms 468 KB Output is correct
6 Correct 408 ms 468 KB Output is correct
7 Correct 737 ms 516 KB Output is correct
8 Correct 759 ms 520 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 31 ms 1720 KB Output is correct
12 Correct 32 ms 1632 KB Output is correct
13 Correct 29 ms 1700 KB Output is correct
14 Correct 28 ms 1700 KB Output is correct
15 Correct 32 ms 1732 KB Output is correct
16 Correct 43 ms 1708 KB Output is correct
17 Correct 29 ms 1792 KB Output is correct
18 Correct 23 ms 1824 KB Output is correct
19 Correct 458 ms 1836 KB Output is correct
20 Correct 454 ms 1740 KB Output is correct
21 Correct 485 ms 1860 KB Output is correct
22 Correct 407 ms 1748 KB Output is correct
23 Correct 443 ms 1732 KB Output is correct
24 Correct 789 ms 1856 KB Output is correct