oj.uz

Submission #923717

# Submission time Handle Problem Language Result Execution time Memory
923717 2024-02-07T15:38:22 Z andrei_boaca Road Construction (JOI21_road_construction) C++17
65 / 100
 9643 ms 2097152 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 x,y;
    long long minim;
    node()
    {
        l=NULL;
        r=NULL;
        x=0;
        y=0;
        minim=0;
        st=0;
        dr=0;
    }
};
node *arb[2][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->minim=INFBIG;
    rez->x=INF;
    rez->y=INF;
    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 x,int y,ll val)
{
    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->x=x;
        rez->y=y;
        rez->minim=val;
        return rez;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        rez->l=update(rez->l,poz,x,y,val);
    else
        rez->r=update(rez->r,poz,x,y,val);
    rez->minim=rez->l->minim;
    rez->x=rez->l->x;
    rez->y=rez->l->y;
    if(rez->r->minim<rez->minim)
    {
        rez->minim=rez->r->minim;
        rez->x=rez->r->x;
        rez->y=rez->r->y;
    }
    return rez;
}
answer query(node *me,int a,int b)
{
    int st=me->st;
    int dr=me->dr;
    if(st>=a&&dr<=b)
        return {me->x,me->y,me->minim};
    answer rez={INF,INF,INFBIG};
    int mij=(st+dr)/2;
    if(a<=mij)
    {
        answer p=query(me->l,a,b);
        if(p.minim<rez.minim)
            rez=p;
    }
    if(b>mij)
    {
        answer p=query(me->r,a,b);
        if(p.minim<rez.minim)
            rez=p;
    }
    return rez;
}
node* add(node *me,int x,int y,int a,int b)
{
    int poz=nrm[y];
    answer rez=query(me,poz,poz);
    ll val=0;
    if(a==0)
        val-=x;
    else
        val+=x;
    if(b==0)
        val-=y;
    else
        val+=y;
    if(val<rez.minim)
        me=update(me,poz,x,y,val);
    return me;
}
node* out(node *me,int x,int y,int a,int b)
{
    int poz=nrm[y];
    answer rez=query(me,poz,poz);
    if(rez.x!=x||rez.y!=y)
        return me;
    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)
        me=update(me,poz,INF,INF,INFBIG);
    else
    {
        ll val=0;
        x=nxt;
        if(a==0)
            val-=x;
        else
            val+=x;
        if(b==0)
            val-=y;
        else
            val+=y;
        me=update(me,poz,x,y,val);
    }
    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][0][ind],1,poz);
    a.minim+=x+y;
    if(a.minim<rez.minim)
        rez=a;
    a=query(arb[0][1][ind],poz,ymax);
    a.minim+=x-y;
    if(a.minim<rez.minim)
        rez=a;
    a=query(arb[1][0][ind],1,poz);
    a.minim+=(-x+y);
    if(a.minim<rez.minim)
        rez=a;
    a=query(arb[1][1][ind],poz,ymax);
    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++)
        for(int j=0;j<=1;j++)
            arb[i][j][1]=build(1,ymax);
    for(int i=2;i<=n;i++)
    {
        arb[1][0][1]=add(arb[1][0][1],v[i].x,v[i].y,1,0);
        arb[1][1][1]=add(arb[1][1][1],v[i].x,v[i].y,1,1);
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=1;j++)
            for(int p=0;p<=1;p++)
                arb[j][p][i]=arb[j][p][i-1];
        arb[1][0][i]=out(arb[1][0][i],v[i].x,v[i].y,1,0);
        arb[1][1][i]=out(arb[1][1][i],v[i].x,v[i].y,1,1);
        arb[0][0][i]=add(arb[0][0][i],v[i-1].x,v[i-1].y,0,0);
        arb[0][1][i]=add(arb[0][1][i],v[i-1].x,v[i-1].y,0,1);
    }
    for(int i=1;i<=n;i++)
    {
        long long val=getmin(i).minim;
        setik.insert({val,i});
    }
    while(k--)
    {
        nrop++;
        int i=(*setik.begin()).second;
        setik.erase(setik.begin());
        answer a=getmin(i);
        sol.push_back(a.minim);
        long long val=a.minim;
        int x=a.x;
        int y=a.y;
        int j=where[{x,y}];
        if(j<i)
        {
            arb[0][0][i]=out(arb[0][0][i],x,y,0,0);
            arb[0][1][i]=out(arb[0][1][i],x,y,0,1);

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

            answer b=getmin(j);
            setik.erase({b.minim,j});
            arb[0][0][j]=out(arb[0][0][j],v[i].x,v[i].y,0,0);
            arb[0][1][j]=out(arb[0][1][j],v[i].x,v[i].y,0,1);
            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 'int main()':
road_construction.cpp:240:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
road_construction.cpp:277:19: warning: unused variable 'val' [-Wunused-variable]
  277 |         long long val=a.minim;
      |                   ^~~
road_construction.cpp:308:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  308 |     for(int i=0;i<sol.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2453 ms 538504 KB Output is correct
2 Correct 2544 ms 538816 KB Output is correct
3 Correct 35 ms 13252 KB Output is correct
4 Correct 36 ms 13256 KB Output is correct
5 Correct 2230 ms 537320 KB Output is correct
6 Correct 10 ms 19036 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 146356 KB Output is correct
2 Correct 1342 ms 146272 KB Output is correct
3 Correct 36 ms 13260 KB Output is correct
4 Correct 488 ms 146440 KB Output is correct
5 Correct 488 ms 146512 KB Output is correct
6 Correct 484 ms 146512 KB Output is correct
7 Correct 526 ms 146000 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5011 ms 1496996 KB Output is correct
2 Correct 5019 ms 1496912 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 221 ms 96308 KB Output is correct
5 Correct 1097 ms 518860 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5011 ms 1496996 KB Output is correct
2 Correct 5019 ms 1496912 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 221 ms 96308 KB Output is correct
5 Correct 1097 ms 518860 KB Output is correct
6 Correct 5065 ms 1496772 KB Output is correct
7 Correct 5091 ms 1497312 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8628 KB Output is correct
10 Correct 4814 ms 1423176 KB Output is correct
11 Correct 224 ms 96184 KB Output is correct
12 Correct 1085 ms 519632 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2453 ms 538504 KB Output is correct
2 Correct 2544 ms 538816 KB Output is correct
3 Correct 35 ms 13252 KB Output is correct
4 Correct 36 ms 13256 KB Output is correct
5 Correct 2230 ms 537320 KB Output is correct
6 Correct 10 ms 19036 KB Output is correct
7 Correct 7853 ms 1408496 KB Output is correct
8 Correct 7838 ms 1408716 KB Output is correct
9 Correct 35 ms 13260 KB Output is correct
10 Correct 4732 ms 1342924 KB Output is correct
11 Correct 5671 ms 1314188 KB Output is correct
12 Correct 1564 ms 717756 KB Output is correct
13 Correct 1784 ms 670576 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2453 ms 538504 KB Output is correct
2 Correct 2544 ms 538816 KB Output is correct
3 Correct 35 ms 13252 KB Output is correct
4 Correct 36 ms 13256 KB Output is correct
5 Correct 2230 ms 537320 KB Output is correct
6 Correct 10 ms 19036 KB Output is correct
7 Correct 1422 ms 146356 KB Output is correct
8 Correct 1342 ms 146272 KB Output is correct
9 Correct 36 ms 13260 KB Output is correct
10 Correct 488 ms 146440 KB Output is correct
11 Correct 488 ms 146512 KB Output is correct
12 Correct 484 ms 146512 KB Output is correct
13 Correct 526 ms 146000 KB Output is correct
14 Correct 5011 ms 1496996 KB Output is correct
15 Correct 5019 ms 1496912 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 221 ms 96308 KB Output is correct
18 Correct 1097 ms 518860 KB Output is correct
19 Correct 5065 ms 1496772 KB Output is correct
20 Correct 5091 ms 1497312 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 2 ms 8628 KB Output is correct
23 Correct 4814 ms 1423176 KB Output is correct
24 Correct 224 ms 96184 KB Output is correct
25 Correct 1085 ms 519632 KB Output is correct
26 Correct 7853 ms 1408496 KB Output is correct
27 Correct 7838 ms 1408716 KB Output is correct
28 Correct 35 ms 13260 KB Output is correct
29 Correct 4732 ms 1342924 KB Output is correct
30 Correct 5671 ms 1314188 KB Output is correct
31 Correct 1564 ms 717756 KB Output is correct
32 Correct 1784 ms 670576 KB Output is correct
33 Runtime error 9643 ms 2097152 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -