oj.uz

Submission #923733

# Submission time Handle Problem Language Result Execution time Memory
923733 2024-02-07T16:52:59 Z andrei_boaca Road Construction (JOI21_road_construction) C++17
100 / 100
 9585 ms 1619256 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1769 ms 361348 KB Output is correct
2 Correct 1806 ms 361240 KB Output is correct
3 Correct 33 ms 13428 KB Output is correct
4 Correct 36 ms 13268 KB Output is correct
5 Correct 1674 ms 360016 KB Output is correct
6 Correct 10 ms 13916 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1508 ms 126784 KB Output is correct
2 Correct 1426 ms 127008 KB Output is correct
3 Correct 34 ms 13268 KB Output is correct
4 Correct 466 ms 126564 KB Output is correct
5 Correct 484 ms 126776 KB Output is correct
6 Correct 479 ms 126924 KB Output is correct
7 Correct 518 ms 125980 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3679 ms 1017100 KB Output is correct
2 Correct 3607 ms 1016600 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 261 ms 95316 KB Output is correct
5 Correct 967 ms 519464 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3679 ms 1017100 KB Output is correct
2 Correct 3607 ms 1016600 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 261 ms 95316 KB Output is correct
5 Correct 967 ms 519464 KB Output is correct
6 Correct 3613 ms 1021916 KB Output is correct
7 Correct 3652 ms 1021760 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 3577 ms 1005800 KB Output is correct
11 Correct 211 ms 92424 KB Output is correct
12 Correct 964 ms 515024 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1769 ms 361348 KB Output is correct
2 Correct 1806 ms 361240 KB Output is correct
3 Correct 33 ms 13428 KB Output is correct
4 Correct 36 ms 13268 KB Output is correct
5 Correct 1674 ms 360016 KB Output is correct
6 Correct 10 ms 13916 KB Output is correct
7 Correct 6481 ms 948788 KB Output is correct
8 Correct 6507 ms 948932 KB Output is correct
9 Correct 34 ms 13508 KB Output is correct
10 Correct 3400 ms 925976 KB Output is correct
11 Correct 4286 ms 914572 KB Output is correct
12 Correct 1379 ms 550588 KB Output is correct
13 Correct 1474 ms 514240 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1769 ms 361348 KB Output is correct
2 Correct 1806 ms 361240 KB Output is correct
3 Correct 33 ms 13428 KB Output is correct
4 Correct 36 ms 13268 KB Output is correct
5 Correct 1674 ms 360016 KB Output is correct
6 Correct 10 ms 13916 KB Output is correct
7 Correct 1508 ms 126784 KB Output is correct
8 Correct 1426 ms 127008 KB Output is correct
9 Correct 34 ms 13268 KB Output is correct
10 Correct 466 ms 126564 KB Output is correct
11 Correct 484 ms 126776 KB Output is correct
12 Correct 479 ms 126924 KB Output is correct
13 Correct 518 ms 125980 KB Output is correct
14 Correct 3679 ms 1017100 KB Output is correct
15 Correct 3607 ms 1016600 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 261 ms 95316 KB Output is correct
18 Correct 967 ms 519464 KB Output is correct
19 Correct 3613 ms 1021916 KB Output is correct
20 Correct 3652 ms 1021760 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 3577 ms 1005800 KB Output is correct
24 Correct 211 ms 92424 KB Output is correct
25 Correct 964 ms 515024 KB Output is correct
26 Correct 6481 ms 948788 KB Output is correct
27 Correct 6507 ms 948932 KB Output is correct
28 Correct 34 ms 13508 KB Output is correct
29 Correct 3400 ms 925976 KB Output is correct
30 Correct 4286 ms 914572 KB Output is correct
31 Correct 1379 ms 550588 KB Output is correct
32 Correct 1474 ms 514240 KB Output is correct
33 Correct 9585 ms 1619256 KB Output is correct
34 Correct 9433 ms 1619088 KB Output is correct
35 Correct 5871 ms 1547436 KB Output is correct
36 Correct 2147 ms 914272 KB Output is correct
37 Correct 2179 ms 914244 KB Output is correct
38 Correct 2355 ms 854672 KB Output is correct