Submission #1147967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147967		ace5	Road Construction (JOI21_road_construction)	C++20	0 / 100	10094 ms	54636 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<ll> segTree;

void build(int l,int r,int indV)
{
    if(l == r)
    {
        segTree[indV] = -INF;
        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;
        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]);
}
vector<int> pos;

void get(int lx,int rx,int x,int l,int r,int indV)
{
    if(l > rx || r < lx || (l >= lx && r <= rx && segTree[indV] < x))
        return ;
    else if(l == r)
    {
        pos.push_back(l);
        return ;
    }
    int m = (l+r)/2;
    get(lx,rx,x,l,m,indV*2+1);
    get(lx,rx,x,m+1,r,indV*2+2);
    return ;
}


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)
{
    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<int>> ts(n);
    vector<ll> ans;
    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);
            modify(events[i].l,events[i].t,0,n-1,0);
        }
        else
        {
            pos.clear();
            get(events[i].l,events[i].r,events[i].t - 2*d,0,n-1,0);
            for(auto ti : pos)
            {
                for(int y = ts[ti].size()-1;y >= 0;--y)
                {
                    if(dist(events[i].i,ts[ti][y]) <= k && events[i].i != ts[ti][y])
                    {
                        ans.push_back(dist(events[i].i,ts[ti][y]));
                    }
                    else
                        break;
                }
            }
        }
    }
    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;
        vector<ll> ans = find_answer(m,k);
        if(ans.size() < 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: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35