Submission #1147968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147968		ace5	Road Construction (JOI21_road_construction)	C++20	100 / 100	5893 ms	67576 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

vector<ll> fenv;

void modifyf(int i,ll x)
{
    for(int j = i;j < fenv.size();j += (j & (-j)))
        fenv[j] += x;
    return ;
}
ll getf(int r)
{
    ll ans = 0;
    for(int j = r;j > 0;j -= (j & (-j)))
        ans += fenv[j];
    return ans;
}

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)const {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;
vector<int> ind;

ll dist(int i,int j)
{
   // cout << i << ' ' << j << ' ' << abs(p[i].first-p[j].first) + abs(p[i].second-p[j].second) << "\n";
    return abs(p[i].first-p[j].first) + abs(p[i].second-p[j].second);
}

vector<ll> find_answer(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 = ind[lower_bound(py.begin(),py.end(),make_pair(p2[i].second - d,ll(-1))) - py.begin()];
        int rg = ind[upper_bound(py.begin(),py.end(),make_pair(p2[i].second,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(events[i].i == ts[tk.second][po[tk.second]])
                {
                    //cout << "! " << tk.first << ' ' << tk.second << endl;
                    ans.pop_back();
                    ch.insert(tk.second);
                    modify(tk.second,-INF,0,n-1,0);
                }
                else
                {
                    if(ans.size() == k)
                    {
                        break;
                    }
                    ch.insert(tk.second);
                    po[tk.second]--;
                    modify(tk.second,(po[tk.second] == -1 ? -INF : p2[ts[tk.second][po[tk.second]]].first),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;
}
ll check(ll d,ll k)
{
    int n = p.size();
    fenv.clear();
    fenv.resize(n+2);
    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 = ind[lower_bound(py.begin(),py.end(),make_pair(p2[i].second - d,ll(-1))) - py.begin()];
        int rg = ind[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));
        events.push_back(event(p2[i].first - d,-1,lg,rg,i));
    }
    sort(events.begin(),events.end());
    ll ans = 0;
    for(int i = 0;i < events.size();++i)
    {
        if(events[i].typ == 0)
        {
            ans += getf(events[i].l+1);
        }
        else if(events[i].typ == -1)
        {
            modifyf(events[i].l+1,1);
            modifyf(events[i].r+2,-1);
        }
        else
        {
            modifyf(events[i].l+1,-1);
            modifyf(events[i].r+2,1);
        }

    }
    return (ans-n)/2;
}

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;
    int ty = 0;
    for(int j = 0;j < n;++j)
    {
        if(j > 0 && py[j].first != py[j-1].first)
            ty++;
        pc[py[j].second].second = ty;
        ind.push_back(ty);
    }
    ll l = 0,r = 4e9;
    while(l < r)
    {
        ll m = (l+r)/2;
        ll ans = check(m,k);
        if(ans < k)
            l = m+1;
        else
            r = m;
    }
    vector<ll> ans = find_answer(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: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35