Submission #1293042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293042		simona1230	Road Construction (JOI21_road_construction)	C++20	38 / 100	922 ms	7648 KiB

road_construction

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

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

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 d)
{
    set<pair<long long,long long> > s;
    long long l=1;
    //cout<<"! "<<x<<endl;
    v.clear();
    for(long long i=2;i<=n;i++)
    {
        pair<long long,long long> sw={p[i-1].second,p[i-1].first};
        s.insert(sw);

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

        auto it=s.lower_bound({p[i].second-d,(long long)-1e9});
        while(it!=s.end()&&it->first<=d+p[i].second)
        {
            pair<long long,long long> c=*it;
            //cout<<"+ "<<c.first<<" "<<c.second<<" "<<p[i].first<<" "<<(*it).first<<endl;
            v.push_back(max(llabs(c.first-p[i].second),llabs(c.second-p[i].first)));
            if(v.size()==k)return 1;
            it++;
        }
        //cout<<i<<" > "<<l<<" "<<r<<endl;
    }

    return 0;
}

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=1e18;
    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: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35