Submission #945872

#	Time	Username	Problem	Language	Result	Execution time	Memory
945872		beepbeepsheep	Road Construction (JOI21_road_construction)	C++17	100 / 100	5754 ms	171480 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif // DEBUG

const ll maxn=2e5+5e4+5;
const ll inf=1e15;
const ll mod=1e9+7;

ll n;
ll x[maxn],y[maxn];
ii ranges[maxn];
vector<ll> pos;
vector<ii> updates;
ll fen[maxn];
void upd(ll x, ll v){
    while (x<maxn){
        fen[x]+=v;
        x+=(x&-x);
    }
}
ll query(ll x){
    ll ans=0;
    while (x){
        ans+=fen[x];
        x-=(x&-x);
    }
    return ans;
}
ll query(ll x, ll y){
    return query(y)-query(x-1);
}
ll check(ll len){
    vector<tuple<ll,ll,ll>> queries;
    for (int i=1;i<=n;i++){
        queries.emplace_back(y[i]-len-1,i,-1);
        //exclusive
        queries.emplace_back(y[i]+len,i,1);
        //inclusive
        ranges[i].first=lower_bound(pos.begin(),pos.end(),x[i]-len)
                        -pos.begin();
        ranges[i].second=upper_bound(pos.begin(),pos.end(),x[i]+len)
                        -pos.begin()-1;
    }
    sort(queries.begin(),queries.end());
    ll ans=0,ptr=0;
    memset(fen,0,sizeof(fen));
    for (auto [a,b,c]:queries){
        while (ptr!=updates.size() &&
               updates[ptr].first<=a){
            upd(updates[ptr].second,1);
            ptr++;
        }
        ans+=c*(query(ranges[b].first,ranges[b].second));
    }
    return (ans-n)/2;
}
struct node{
    ll s,e,m;
    vector<ii> v;
    node *l,*r;
    node(ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1;
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ii p){
        if (s==e){
            v.emplace_back(p);
            return;
        }
        if (x>m) r->upd(x,p);
        else l->upd(x,p);
    }
    void build(){
        if (s!=e){
            l->build(),r->build();
            for (auto u:l->v) v.emplace_back(u);
            for (auto u:r->v) v.emplace_back(u);
        }
        sort(v.begin(),v.end()); //remember to put y first
    }
    vector<ll> query(ll x, ll y, ll v1, ll v2, ii p){
        if (x<=s && e<=y){
            ll x1,y1;
            tie(y1,x1)=p;
            ll lb=lower_bound(v.begin(),v.end(),
                              make_pair(v1,-inf))-v.begin();
            ll ub=upper_bound(v.begin(),v.end(),
                              make_pair(v2,inf))-v.begin();
            vector<ll> out;
            for (int i=lb;i<ub;i++){
                ll x2,y2;
                tie(y2,x2)=v[i];
                if (x1==x2 && y1==y2) continue;
                out.emplace_back(max(abs(x1-x2),abs(y1-y2)));
            }
            return out;
        }
        if (x>m) return r->query(x,y,v1,v2,p);
        if (y<=m) return l->query(x,y,v1,v2,p);
        vector<ll> out1=l->query(x,y,v1,v2,p);
        vector<ll> out2=r->query(x,y,v1,v2,p);
        for (auto u:out1) out2.emplace_back(u);
        return out2;
    }
}*root;
ll flat[maxn];
vector<ll> out;
void solve(ll len){
    for (int i=1;i<=n;i++){
        ranges[i].first=lower_bound(pos.begin(),pos.end(),x[i]-len)
                        -pos.begin();
        ranges[i].second=upper_bound(pos.begin(),pos.end(),x[i]+len)
                        -pos.begin()-1;
    }
    root=new node(1,n);
    for (int i=1;i<=n;i++){
        root->upd(flat[i],make_pair(y[i],x[i]));
    }
    root->build();
    for (int i=1;i<=n;i++){
        ll l,r;
        tie(l,r)=ranges[i];
        vector<ll> roads=root->query(l,r,y[i]-len,
                                     y[i]+len,make_pair(y[i],x[i]));
        //left x, right x, bottom y, top y, central point
        for (auto u:roads) out.emplace_back(u);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll a,b,k;
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a>>b;
        x[i]=a+b,y[i]=a-b;
        pos.emplace_back(x[i]);
    }
    pos.emplace_back(-inf);
    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    for (int i=1;i<=n;i++){
        flat[i]=lower_bound(pos.begin(),pos.end(),x[i])
                -pos.begin();
        updates.emplace_back(y[i],flat[i]);
    }
    sort(updates.begin(),updates.end());
    ll l=1,r=4'000'000'005,m;
    while (l!=r-1){
        m=(l+r)>>1;
        if (check(m)>=k) r=m; //we need to reach r
        else l=m;
    }
    //find everything <=l
    solve(l);
    sort(out.begin(),out.end());
    while (out.size()<2*k) out.emplace_back(r);
    for (int i=0;i<out.size();i+=2) cout<<out[i]<<endl;
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'long long int check(long long int)':
road_construction.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while (ptr!=updates.size() &&
      |                ~~~^~~~~~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:165:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  165 |     while (out.size()<2*k) out.emplace_back(r);
      |            ~~~~~~~~~~^~~~
road_construction.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for (int i=0;i<out.size();i+=2) cout<<out[i]<<endl;
      |                  ~^~~~~~~~~~~

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