Submission #541672

#	Time	Username	Problem	Language	Result	Execution time	Memory
541672		Fysty	Road Construction (JOI21_road_construction)	C++17	100 / 100	5087 ms	20400 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
const ll INF=3e18;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end());uni(c)
const ll C=4e9;
const int N=250005;

ll n,k;
vector<pll> p;
vector<ll> v;

struct BIT
{
    ll sz,a[N];
    void init()
    {
        rep1(i,sz) a[i]=0;
    }
    void upd(ll x,ll val)
    {
        for(;x<=sz;x+=x&-x) a[x]+=val;
    }
    ll qry(ll x)
    {
        ll ret=0;
        for(;x;x-=x&-x) ret+=a[x];
        return ret;
    }
} bit;

ll calc(ll d)
{
    ll ret=0;
    ll l=0;
    bit.init();
    rep(i,n)
    {
        while(l<i&&p[i].F-p[l].F>d)
        {
            ll id=lower_bound(v.begin(),v.end(),p[l].S)-v.begin()+1;
            bit.upd(id,-1);
            l++;
        }
        ll ql=lower_bound(v.begin(),v.end(),p[i].S-d)-v.begin()+1;
        ll qr=upper_bound(v.begin(),v.end(),p[i].S+d)-v.begin();
        ret+=bit.qry(qr)-bit.qry(ql-1);
        ll id=lower_bound(v.begin(),v.end(),p[i].S)-v.begin()+1;
        bit.upd(id,1);
    }
    return ret;
}

void getans(ll d,ll k)
{
    if(d==0)
    {
        rep(i,k) cout<<"0\n";
        return;
    }
    vector<ll> ans;
    multiset<pll> s;
    ll l=0;
    rep(i,n)
    {
        while(l<i&&p[i].F-p[l].F>d-1)
        {
            s.erase(s.find({p[l].S,p[l].F}));
            l++;
        }
        auto qr=s.upper_bound({p[i].S+d-1,INF});
        for(auto it=s.lower_bound({p[i].S-d+1,-INF});it!=qr;it++)
        {
            pll q=*it;
            swap(q.F,q.S);
            ans.pb(max(abs(q.F-p[i].F),abs(q.S-p[i].S)));
        }
        s.insert({p[i].S,p[i].F});
    }
    sort(ans.begin(),ans.end());
    for(ll u:ans) cout<<u<<"\n";
    ll r=k-ans.size();
    rep(_,r) cout<<d<<"\n";
}
signed main()
{
    MottoHayaku

    cin>>n>>k;
    rep(i,n)
    {
        ll X,Y;
        cin>>X>>Y;
        p.pb({X-Y,X+Y});
        v.pb(X+Y);
    }
    unisort(v);
    sort(p.begin(),p.end());
    ll l=1,r=C;
    bit.sz=v.size();
    while(l<r)
    {
        ll mid=l+r>>1;
        ll tmp=calc(mid);
        if(tmp<k) l=mid+1;
        else r=mid;
    }
    getans(l,k);
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:116:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         ll mid=l+r>>1;
      |                ~^~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35