Submission #923733

#	Time	Username	Problem	Language	Result	Execution time	Memory
923733		andrei_boaca	Road Construction (JOI21_road_construction)	C++17	100 / 100	9585 ms	1619256 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=2e9+5;
const ll INFBIG=5e9;
int n,k,ymax;
map<int,int> nrm;
map<pii,int> where;
set<pair<long long,int>> setik;
int nrop=0;
struct point
{
    int x,y;
} v[250005];
bool byx(point a,point b)
{
    return a.x<b.x;
}
vector<int> vals;
vector<int> myx[250005];
struct node
{
    node *l,*r;
    int st,dr;
    int x1,y1;
    int x2,y2;
    long long minim1,minim2;
    node()
    {
        l=NULL;
        r=NULL;
        x1=0;
        y1=0;
        minim1=0;
        x2=0;
        y2=0;
        minim2=0;
        st=0;
        dr=0;
    }
};
node *arb[2][250005]; /// [xmic,xmare][ymic,ymare]
struct answer
{
    int x,y;
    long long minim;
};
node *build(int st,int dr)
{
    node *rez=new node;
    rez->st=st;
    rez->dr=dr;
    rez->minim1=INFBIG;
    rez->x1=INF;
    rez->y1=INF;
    rez->x2=INF;
    rez->y2=INF;
    rez->minim2=INFBIG;
    if(st==dr)
        return rez;
    int mij=(st+dr)/2;
    rez->l=build(st,mij);
    rez->r=build(mij+1,dr);
    return rez;
}
node *update(node *me,int poz,int x1,int y1,ll val1,int x2,int y2,ll val2)
{
    int st=me->st;
    int dr=me->dr;
    node *rez=new node;
    rez->st=st;
    rez->dr=dr;
    rez->l=me->l;
    rez->r=me->r;
    if(st==dr)
    {
        rez->x1=x1;
        rez->y1=y1;
        rez->minim1=val1;
        rez->x2=x2;
        rez->y2=y2;
        rez->minim2=val2;
        return rez;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        rez->l=update(rez->l,poz,x1,y1,val1,x2,y2,val2);
    else
        rez->r=update(rez->r,poz,x1,y1,val1,x2,y2,val2);
    rez->minim1=rez->l->minim1;
    rez->x1=rez->l->x1;
    rez->y1=rez->l->y1;
    if(rez->r->minim1<rez->minim1)
    {
        rez->minim1=rez->r->minim1;
        rez->x1=rez->r->x1;
        rez->y1=rez->r->y1;
    }

    rez->minim2=rez->l->minim2;
    rez->x2=rez->l->x2;
    rez->y2=rez->l->y2;
    if(rez->r->minim2<rez->minim2)
    {
        rez->minim2=rez->r->minim2;
        rez->x2=rez->r->x2;
        rez->y2=rez->r->y2;
    }
    return rez;
}
answer query(node *me,int a,int b,int who)
{
    int st=me->st;
    int dr=me->dr;
    if(st>=a&&dr<=b)
    {
        if(who==1)
            return {me->x1,me->y1,me->minim1};
        if(who==2)
            return {me->x2,me->y2,me->minim2};
    }
    answer rez={INF,INF,INFBIG};
    int mij=(st+dr)/2;
    if(a<=mij)
    {
        answer p=query(me->l,a,b,who);
        if(p.minim<rez.minim)
            rez=p;
    }
    if(b>mij)
    {
        answer p=query(me->r,a,b,who);
        if(p.minim<rez.minim)
            rez=p;
    }
    return rez;
}
node* add(node *me,int x,int y,int a)
{
    int poz=nrm[y];
    answer rez=query(me,poz,poz,1);
    int x1=rez.x,y1=rez.y;
    ll minim1=rez.minim;

    rez=query(me,poz,poz,2);
    int x2=rez.x,y2=rez.y;
    ll minim2=rez.minim;
    ll val=0;
    if(a==0)
        val-=x;
    else
        val+=x;
    /// b==0
    val-=y;
    if(val<minim1)
    {
        x1=x;
        y1=y;
        minim1=val;
    }
    val=0;
    if(a==0)
        val-=x;
    else
        val+=x;
    /// b==1
    val+=y;
    if(val<minim2)
    {
        x2=x;
        y2=y;
        minim2=val;
    }
    me=update(me,poz,x1,y1,minim1,x2,y2,minim2);
    return me;
}
node* out(node *me,int x,int y,int a)
{
    bool dbg=0;
    if(x==1812&&y==-9841)
        dbg=1;
    bool found=0;
    int poz=nrm[y];
    answer rez=query(me,poz,poz,1);
    ll x1=rez.x;
    ll y1=rez.y;
    ll minim1=rez.minim;
    int b=0;
    if(rez.x==x&&rez.y==y)
    {
        found=1;
        int nxt=INF;
        if(a==0)
        {
            int st=0;
            int dr=myx[poz].size();
            dr--;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(myx[poz][mij]<x)
                {
                    nxt=myx[poz][mij];
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
        }
        else
        {
            int st=0;
            int dr=myx[poz].size();
            dr--;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(myx[poz][mij]>x)
                {
                    nxt=myx[poz][mij];
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
        }
        if(nxt==INF)
        {
            x1=INF;
            y1=INF;
            minim1=INFBIG;
        }
        else
        {
            ll val=0;
            x1=nxt;
            if(a==0)
                val-=x1;
            else
                val+=x1;
            if(b==0)
                val-=y1;
            else
                val+=y1;
            y1=y;
            minim1=val;
        }
    }
    rez=query(me,poz,poz,2);
    ll x2=rez.x;
    ll y2=rez.y;
    ll minim2=rez.minim;
    b=1;
    if(rez.x==x&&rez.y==y)
    {
        found=1;
        int nxt=INF;
        if(a==0)
        {
            int st=0;
            int dr=myx[poz].size();
            dr--;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(myx[poz][mij]<x)
                {
                    nxt=myx[poz][mij];
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
        }
        else
        {
            int st=0;
            int dr=myx[poz].size();
            dr--;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(myx[poz][mij]>x)
                {
                    nxt=myx[poz][mij];
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
        }
        if(nxt==INF)
        {
            x2=INF;
            y2=INF;
            minim2=INFBIG;
        }
        else
        {
            ll val=0;
            x2=nxt;
            if(a==0)
                val-=x2;
            else
                val+=x2;
            if(b==0)
                val-=y2;
            else
                val+=y2;
            y2=y;
            minim2=val;
        }
    }
    if(!found)
        return me;
    me=update(me,poz,x1,y1,minim1,x2,y2,minim2);
    return me;
}
answer getmin(int ind)
{
    answer rez={INF,INF,INFBIG};
    int x=v[ind].x,y=v[ind].y;
    int poz=nrm[y];
    answer a=query(arb[0][ind],1,poz,1);
    a.minim+=x+y;
    if(a.minim<rez.minim)
        rez=a;
    a=query(arb[0][ind],poz,ymax,2);
    a.minim+=x-y;
    if(a.minim<rez.minim)
        rez=a;
    a=query(arb[1][ind],1,poz,1);
    a.minim+=(-x+y);
    if(a.minim<rez.minim)
        rez=a;
    a=query(arb[1][ind],poz,ymax,2);
    a.minim+=(-x-y);
    if(a.minim<rez.minim)
        rez=a;
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        vals.push_back(v[i].y);
    }
    vector<long long> sol;
    if(k==n*(n-1)/2)
    {
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                sol.push_back(abs(v[i].x-v[j].x)*1LL+1LL*abs(v[i].y-v[j].y));
        sort(sol.begin(),sol.end());
        for(auto i:sol)
            cout<<i<<'\n';
        return 0;
    }
    sort(v+1,v+n+1,byx);
    for(int i=1;i<=n;i++)
        where[{v[i].x,v[i].y}]=i;
    sort(vals.begin(),vals.end());
    vals.erase(unique(vals.begin(),vals.end()),vals.end());
    for(int i=0;i<vals.size();i++)
    {
        nrm[vals[i]]=i+1;
        ymax=i+1;
    }
    for(int i=1;i<=n;i++)
        myx[nrm[v[i].y]].push_back(v[i].x);
    for(int i=0;i<=1;i++)
        arb[i][1]=build(1,ymax);
    for(int i=2;i<=n;i++)
        arb[1][1]=add(arb[1][1],v[i].x,v[i].y,1);
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=1;j++)
            arb[j][i]=arb[j][i-1];
        arb[1][i]=out(arb[1][i],v[i].x,v[i].y,1);
        arb[0][i]=add(arb[0][i],v[i-1].x,v[i-1].y,0);
    }
    for(int i=1;i<=n;i++)
    {
        long long val=getmin(i).minim;
        //assert(val>0);
        setik.insert({val,i});
    }
    while(k--)
    {
        int i=(*setik.begin()).second;
        setik.erase(setik.begin());
        answer a=getmin(i);
        sol.push_back(a.minim);
        long long val=a.minim;
        //assert(val>0);
        int x=a.x;
        int y=a.y;
        int j=where[{x,y}];
        if(j<i)
        {
            arb[0][i]=out(arb[0][i],x,y,0);

            answer b=getmin(j);
            setik.erase({b.minim,j});
            arb[1][j]=out(arb[1][j],v[i].x,v[i].y,1);
            b=getmin(j);
            setik.insert({b.minim,j});
        }
        else
        {
            arb[1][i]=out(arb[1][i],x,y,1);

            answer b=getmin(j);
            setik.erase({b.minim,j});
            arb[0][j]=out(arb[0][j],v[i].x,v[i].y,0);
            b=getmin(j);
            setik.insert({b.minim,j});
        }
        a=getmin(i);
        setik.insert({a.minim,i});
    }
    for(int i=0;i<sol.size();i++)
        cout<<sol[i]<<'\n';
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'node* out(node*, int, int, int)':
road_construction.cpp:181:10: warning: variable 'dbg' set but not used [-Wunused-but-set-variable]
  181 |     bool dbg=0;
      |          ^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:370:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  370 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
road_construction.cpp:400:19: warning: unused variable 'val' [-Wunused-variable]
  400 |         long long val=a.minim;
      |                   ^~~
road_construction.cpp:428:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  428 |     for(int i=0;i<sol.size();i++)
      |                 ~^~~~~~~~~~~

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