Submission #446988

#	Time	Username	Problem	Language	Result	Execution time	Memory
446988		jk410	Road Construction (JOI21_road_construction)	C++17	100 / 100	5515 ms	184944 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;
    deque<int> Y[250001];
    void init(){
        for (register 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 ((ll)Point[i].y-Point[s].y>m){
                update(Point[s].idx,-1);
                if (flag)
                    Y[Point[s].idx].pop_front();
                s++;
            }
            int l=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x-m)-Cor_X.begin(),r=upper_bound(Cor_X.begin(),Cor_X.end(),Point[i].x+m)-Cor_X.begin()-1;
            if (l<=r)
                ret+=query(l,r);
            if (flag){
                for (int t=l; t<=r; t++){
                    for (int y:Y[t]){
                        Dist.push_back(max(abs((ll)Point[i].x-Cor_X[t]),(ll)Point[i].y-y));
                        Cnt--;
                    }
                }
                Y[Point[i].idx].push_back(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)/2;
            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;
    }

Compilation message (stderr)

road_construction.cpp: In function 'void init()':
road_construction.cpp:21:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   21 |         for (register int i=1; i<(Tree_size<<1); i++)
      |                           ^

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