Submission #1147903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147903		ace5	Road Construction (JOI21_road_construction)	C++20	0 / 100	10092 ms	68448 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

struct event
{
    event(ll _t,int _typ,int _l,int _r,int _i){t = _t;typ = _typ;l = _l;r = _r;i = _i;};
    ll t;
    int typ;
    int l,r;
    int i;
    bool operator < (const event & oth){return (t != oth.t ? t < oth.t : typ < oth.typ);};
};

vector<pair<ll,int>> segTree;
vector<ll> a;

void build(int l,int r,int indV)
{
    if(l == r)
    {
        segTree[indV] = {a[l],l};
        return ;
    }
    int m =(l+r)/2;
    build(l,m,indV*2+1);
    build(m+1,r,indV*2+2);
    segTree[indV] = max(segTree[indV*2+1],segTree[indV*2+2]);
    return;
}

void modify(int i,ll x,int l,int r,int indV)
{
    if(l > i || r < i)
        return ;
    else if(l == r)
    {
        segTree[indV] = {x,l};
        return ;
    }
    int m = (l+r)/2;
    modify(i,x,l,m,indV*2+1);
    modify(i,x,m+1,r,indV*2+2);
    segTree[indV] = max(segTree[indV*2+1],segTree[indV*2+2]);
}
pair<ll,int> get(int lx,int rx,int l,int r,int indV)
{
    if(l > rx || r < lx)
        return {-INF,-1};
    else if(l >= lx && r <= rx)
        return segTree[indV];
    int m = (l+r)/2;
    pair<ll,int> sl = get(lx,rx,l,m,indV*2+1);
    pair<ll,int> sr = get(lx,rx,m+1,r,indV*2+2);
    return max(sl,sr);
}


vector<pair<ll,ll>> p;
vector<pair<ll,ll>> p2;
vector<pair<ll,ll>> pc;
vector<pair<ll,ll>> py;

ll dist(int i,int j)
{
    return abs(p[i].first-p[j].first) + abs(p[i].second-p[j].second);
}

vector<ll> check(ll d,ll k)
{
    int n = p.size();
    segTree.clear();
    segTree.resize(4*p.size());
    vector<event> events;
    for(int i = 0;i < n;++i)
    {
        events.push_back(event(p2[i].first,0,pc[i].second,pc[i].second,i));
        int lg = lower_bound(py.begin(),py.end(),make_pair(p2[i].second - d,ll(-1))) - py.begin();
        int rg = upper_bound(py.begin(),py.end(),make_pair(p2[i].second + d,ll(p.size())+1)) - py.begin()-1;
        events.push_back(event(p2[i].first + d,1,lg,rg,i));
    }
    sort(events.begin(),events.end());
    vector<vector<ll>> ts(n);
    vector<int> po(n,-1);
    vector<ll> ans;
    a.clear();
    a.resize(n);
    for(int i = 0;i < n;++i)
    {
        a[i] = -INF;
    }
    build(0,n-1,0);
    for(int i = 0;i < events.size();++i)
    {
        if(events[i].typ == 0)
        {
            ts[events[i].l].push_back(events[i].i);
            po[events[i].l] ++;
            a[events[i].l] = events[i].t;
            modify(events[i].l,a[events[i].l],0,n-1,0);
        }
        else
        {
            set<int> ch;
            while(true)
            {
                pair<ll,int> tk = get(events[i].l,events[i].r,0,n-1,0);
                if(tk.first < p2[events[i].i].first - d)
                    break;
                ans.push_back(dist(events[i].i,ts[tk.second][po[tk.second]]));
                if(ans.back() == 0 || events[i].i > ts[tk.second][po[tk.second]])
                {
                    ans.pop_back();
                }
                if(ans.size() == k)
                {
                    break;
                }
                ch.insert(tk.second);
                po[tk.second]--;
                modify(tk.second,(po[tk.second] == -1 ? -INF : ts[tk.second][po[tk.second]]),0,n-1,0);
            }
            if(ans.size() == k)
                break;
            for(auto y:ch)
            {
                po[y] = int(ts[y].size())-1;
                modify(y,a[y],0,n-1,0);
            }
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,k;
    cin >> n >> k;
    for(int j = 0;j < n;++j)
    {
        ll x,y;
        cin >> x >> y;
        p.push_back({x,y});
        p2.push_back({x+y,x-y});
        py.push_back({x-y,j});
    }
    sort(py.begin(),py.end());
    pc = p2;
    for(int j = 0;j < n;++j)
        pc[py[j].second].second = j;
    ll l = 0,r = 1e10;
    while(l < r)
    {
        int m = (l+r)/2;
        vector<ll> ans = check(m,k);
        if(ans.size() < k)
            l = m+1;
        else
            r = m;
    }
    vector<ll> ans = check(l-1,k);
    sort(ans.begin(),ans.end());
    for(int j = 0;j < ans.size();++j)
    {
        cout << ans[j] << "\n";
    }
    for(int j = 0;j < k-ans.size();++j)
    {
        cout << l << "\n";
    }
    cout << "\n";
}

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