Submission #446971

#	Time	Username	Problem	Language	Result	Execution time	Memory
446971		jk410	Road Construction (JOI21_road_construction)	C++17	38 / 100	10010 ms	25388 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point{
    int x,y,idx;
    bool operator<(const point &t)const{
        if (y!=t.y)
            return y<t.y;
        return x<t.x;
    }
};
const int Tree_size=1<<18;
const ll INF=4e9;
int N,Cnt,Size;
ll K,Ans;
int Tree[Tree_size<<1],L[250001],R[250001];
point Point[250001];
vector<ll> Cor_X,Dist;
set<int> S[250001];
void init(){
    for (int i=1; i<(Tree_size<<1); i++)
        Tree[i]=0;
}
void update(int idx,int v){
    for (idx+=Tree_size; idx; idx>>=1)
        Tree[idx]+=v;
}
int query(int l,int r){
    int ret=0;
    for (l+=Tree_size,r+=Tree_size; l<=r; l>>=1,r>>=1){
        if (l&1)
            ret+=Tree[l++];
        if (!(r&1))
            ret+=Tree[r--];
    }
    return ret;
}
ll f(ll m,bool flag){
    ll ret=0;
    init();
    for (int i=1,s=1; i<=N; i++){
        while (Point[i].y-Point[s].y>m){
            update(Point[s].idx,-1);
            if (flag)
                S[Point[s].idx].erase(S[Point[s].idx].find(Point[s].y));
            s++;
        }
        int l=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x-m)-Cor_X.begin(),r;
        auto it=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x+m);
        if (it==Cor_X.end())
            r=Size-1;
        else if (*it==Point[i].x+m)
            r=it-Cor_X.begin();
        else
            r=it-Cor_X.begin()-1;
        if (l<=r)
            ret+=query(l,r);
        if (flag){
            for (int t=l; t<=r; t++){
                for (int y:S[t]){
                    Dist.push_back(max(abs((ll)Point[i].x-Cor_X[t]),(ll)Point[i].y-y));
                    Cnt--;
                }
            }
            S[Point[i].idx].insert(Point[i].y);
        }
        update(Point[i].idx,1);
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>K;
    for (int i=1; i<=N; i++){
        int x,y;
        cin>>x>>y;
        Point[i]={x+y,x-y};
        Cor_X.push_back(Point[i].x);
    }
    sort(Point+1,Point+N+1);
    sort(Cor_X.begin(),Cor_X.end());
    Cor_X.erase(unique(Cor_X.begin(),Cor_X.end()),Cor_X.end());
    Size=Cor_X.size();
    for (int i=1; i<=N; i++)
        Point[i].idx=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x)-Cor_X.begin();
    ll l=0,r=INF;
    while (l<=r){
        ll m=(l+r)>>1;
        if (f(m,false)>=K){
            Ans=m;
            r=m-1;
        }
        else
            l=m+1;
    }
    Cnt=K;
    f(Ans-1,true);
    sort(Dist.begin(),Dist.end());
    for (ll i:Dist)
        cout<<i<<"\n";
    while (Cnt--)
        cout<<Ans<<"\n";
    return 0;
}

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