oj.uz

Submission #923695

# Submission time Handle Problem Language Result Execution time Memory
923695 2024-02-07T15:16:17 Z andrei_boaca Road Construction (JOI21_road_construction) C++17
65 / 100
 9400 ms 2097152 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=1e10;
ll n,k,ymax;
map<int,int> nrm;
map<pii,int> where;
set<pii> setik;
struct point
{
    ll 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;
    ll st,dr;
    ll x,y,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
{
    ll x,y,minim;
};
node *build(int st,int dr)
{
    node *rez=new node;
    rez->st=st;
    rez->dr=dr;
    rez->minim=INF;
    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,ll x,ll y,ll val)
{
    ll st=me->st;
    ll 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;
    }
    ll 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)
{
    ll st=me->st;
    ll dr=me->dr;
    if(st>=a&&dr<=b)
        return {me->x,me->y,me->minim};
    answer rez={INF,INF,INF};
    ll 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,ll x,ll y,ll a,ll b)
{
    ll 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,ll x,ll y,ll a,ll b)
{
    ll poz=nrm[y];
    answer rez=query(me,poz,poz);
    if(rez.x!=x||rez.y!=y)
        return me;
    ll nxt=INF;
    if(a==0)
    {
        ll st=0;
        ll dr=myx[poz].size();
        dr--;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(myx[poz][mij]<x)
            {
                nxt=myx[poz][mij];
                st=mij+1;
            }
            else
                dr=mij-1;
        }
    }
    else
    {
        ll st=0;
        ll dr=myx[poz].size();
        dr--;
        while(st<=dr)
        {
            ll 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,INF);
    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(ll ind)
{
    answer rez={INF,INF,INF};
    ll x=v[ind].x,y=v[ind].y;
    ll 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<ll> 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)+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++)
    {
        ll val=getmin(i).minim;
        setik.insert({val,i});
    }
    k*=2;
    while(k--)
    {
        ll i=(*setik.begin()).second;
        setik.erase(setik.begin());
        answer a=getmin(i);
        sol.push_back(a.minim);
        ll val=a.minim;
        ll x=a.x;
        ll y=a.y;
        if(where[{x,y}]<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);
        }
        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);
        }
        a=getmin(i);
        if(a.minim<=2e9)
            setik.insert({a.minim,i});
    }
    for(int i=0;i<sol.size();i+=2)
        cout<<sol[i]<<'\n';
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:236:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
road_construction.cpp:273:12: warning: unused variable 'val' [-Wunused-variable]
  273 |         ll val=a.minim;
      |            ^~~
road_construction.cpp:290:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  290 |     for(int i=0;i<sol.size();i+=2)
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3082 ms 713432 KB Output is correct
2 Correct 2974 ms 713392 KB Output is correct
3 Correct 34 ms 13364 KB Output is correct
4 Correct 40 ms 13424 KB Output is correct
5 Correct 2987 ms 711960 KB Output is correct
6 Correct 15 ms 20312 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 180856 KB Output is correct
2 Correct 1562 ms 180700 KB Output is correct
3 Correct 39 ms 13088 KB Output is correct
4 Correct 524 ms 180516 KB Output is correct
5 Correct 518 ms 180780 KB Output is correct
6 Correct 610 ms 180884 KB Output is correct
7 Correct 552 ms 180176 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5601 ms 1971640 KB Output is correct
2 Correct 5451 ms 1976452 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 270 ms 112736 KB Output is correct
5 Correct 1295 ms 678412 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5601 ms 1971640 KB Output is correct
2 Correct 5451 ms 1976452 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 270 ms 112736 KB Output is correct
5 Correct 1295 ms 678412 KB Output is correct
6 Correct 5818 ms 1976476 KB Output is correct
7 Correct 5603 ms 1976392 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 5455 ms 1878572 KB Output is correct
11 Correct 228 ms 112984 KB Output is correct
12 Correct 1323 ms 679408 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3082 ms 713432 KB Output is correct
2 Correct 2974 ms 713392 KB Output is correct
3 Correct 34 ms 13364 KB Output is correct
4 Correct 40 ms 13424 KB Output is correct
5 Correct 2987 ms 711960 KB Output is correct
6 Correct 15 ms 20312 KB Output is correct
7 Correct 9358 ms 1866496 KB Output is correct
8 Correct 9400 ms 1866372 KB Output is correct
9 Correct 35 ms 13232 KB Output is correct
10 Correct 5284 ms 1780208 KB Output is correct
11 Correct 6646 ms 1741528 KB Output is correct
12 Correct 1702 ms 947912 KB Output is correct
13 Correct 1889 ms 885648 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3082 ms 713432 KB Output is correct
2 Correct 2974 ms 713392 KB Output is correct
3 Correct 34 ms 13364 KB Output is correct
4 Correct 40 ms 13424 KB Output is correct
5 Correct 2987 ms 711960 KB Output is correct
6 Correct 15 ms 20312 KB Output is correct
7 Correct 1445 ms 180856 KB Output is correct
8 Correct 1562 ms 180700 KB Output is correct
9 Correct 39 ms 13088 KB Output is correct
10 Correct 524 ms 180516 KB Output is correct
11 Correct 518 ms 180780 KB Output is correct
12 Correct 610 ms 180884 KB Output is correct
13 Correct 552 ms 180176 KB Output is correct
14 Correct 5601 ms 1971640 KB Output is correct
15 Correct 5451 ms 1976452 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 270 ms 112736 KB Output is correct
18 Correct 1295 ms 678412 KB Output is correct
19 Correct 5818 ms 1976476 KB Output is correct
20 Correct 5603 ms 1976392 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 5455 ms 1878572 KB Output is correct
24 Correct 228 ms 112984 KB Output is correct
25 Correct 1323 ms 679408 KB Output is correct
26 Correct 9358 ms 1866496 KB Output is correct
27 Correct 9400 ms 1866372 KB Output is correct
28 Correct 35 ms 13232 KB Output is correct
29 Correct 5284 ms 1780208 KB Output is correct
30 Correct 6646 ms 1741528 KB Output is correct
31 Correct 1702 ms 947912 KB Output is correct
32 Correct 1889 ms 885648 KB Output is correct
33 Runtime error 6365 ms 2097152 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -