Submission #1293011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293011		simona1230	Road Construction (JOI21_road_construction)	C++20	0 / 100	6311 ms	2107588 KiB

road_construction

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

long long n,k;
pair<long long,long long> p[250001];

void read()
{
    cin>>n>>k;
    for(long long i=1;i<=n;i++)
    {
        cin>>p[i].first>>p[i].second;
        long long x=p[i].first;
        long long y=p[i].second;
        p[i].first=x-y;
        p[i].second=x+y;
    }
    sort(p+1,p+n+1);
}

vector<long long> v;
bool check(long long x)
{
    set<pair<long long,long long> > s;
    long long l=1,r=1;
    //cout<<"! "<<x<<endl;
    v.clear();
    for(long long i=1;i<=n;i++)
    {
        //cout<<i<<" > "<<l<<" "<<r<<endl;
        while(r<i&&p[i].first-p[r].first<=x)
        {
            pair<long long,long long> sw={p[r].second,p[r].first};
            s.insert(sw);
            r++;
        }

        while(l<r&&p[i].first-p[l].first>x)
        {
            pair<long long,long long> sw={p[l].second,p[l].first};
            s.erase(sw);
            l++;
        }

        auto it=s.lower_bound({p[i].second-x,(long long)-1e9});
        while(it!=s.end()&&abs((*it).first-p[i].second)<=x)
        {
            pair<long long,long long> c=*it;
            v.push_back(max(abs(c.first-p[i].second),abs(c.second-p[i].first)));
            it++;
        }
    }

    return v.size()>=k;
}

void solve()
{
    //for(int i=1;i<=n;i++)
    //    cout<<p[i].first<<" "<<p[i].second<<endl;
    long long d=0;
    long long l=0,r=2*1e9;
    while(l<=r)
    {
        long long m=(l+r)/2;
        //cout<<m<<endl;
        if(check(m))
        {
            d=m;
            r=m-1;
        }
        else l=m+1;
    }

    check(d-1);
    sort(v.begin(),v.end());
    for(long long i=0;i<v.size();i++)
        cout<<v[i]<<endl;
    for(long long i=v.size();i<k;i++)
        cout<<d<<endl;
}

int main()
{
    read();
    solve();
    return 0;
}

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