oj.uz

답안 #923709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923709 2024-02-07T15:29:54 Z andrei_boaca Road Construction (JOI21_road_construction) C++17
65 / 100
 9853 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;
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});
    }
    k*=2;
    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;
        int x=a.x;
        int 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);
        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:239:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
road_construction.cpp:276:19: warning: unused variable 'val' [-Wunused-variable]
  276 |         long long val=a.minim;
      |                   ^~~
road_construction.cpp:292:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  292 |     for(int i=0;i<sol.size();i+=2)
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2464 ms 540384 KB Output is correct
2 Correct 2531 ms 540320 KB Output is correct
3 Correct 34 ms 13252 KB Output is correct
4 Correct 34 ms 13352 KB Output is correct
5 Correct 2379 ms 538964 KB Output is correct
6 Correct 10 ms 19032 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1383 ms 148408 KB Output is correct
2 Correct 1361 ms 148616 KB Output is correct
3 Correct 36 ms 13256 KB Output is correct
4 Correct 485 ms 148040 KB Output is correct
5 Correct 481 ms 148824 KB Output is correct
6 Correct 498 ms 148548 KB Output is correct
7 Correct 523 ms 147720 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5217 ms 1497324 KB Output is correct
2 Correct 5098 ms 1496760 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 224 ms 99156 KB Output is correct
5 Correct 1121 ms 523728 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5217 ms 1497324 KB Output is correct
2 Correct 5098 ms 1496760 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 224 ms 99156 KB Output is correct
5 Correct 1121 ms 523728 KB Output is correct
6 Correct 5131 ms 1496984 KB Output is correct
7 Correct 5145 ms 1496784 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 4967 ms 1423140 KB Output is correct
11 Correct 218 ms 96340 KB Output is correct
12 Correct 1095 ms 519308 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2464 ms 540384 KB Output is correct
2 Correct 2531 ms 540320 KB Output is correct
3 Correct 34 ms 13252 KB Output is correct
4 Correct 34 ms 13352 KB Output is correct
5 Correct 2379 ms 538964 KB Output is correct
6 Correct 10 ms 19032 KB Output is correct
7 Correct 8349 ms 1410396 KB Output is correct
8 Correct 8173 ms 1410436 KB Output is correct
9 Correct 34 ms 13308 KB Output is correct
10 Correct 4665 ms 1345092 KB Output is correct
11 Correct 5788 ms 1316064 KB Output is correct
12 Correct 1505 ms 719716 KB Output is correct
13 Correct 1720 ms 672460 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2464 ms 540384 KB Output is correct
2 Correct 2531 ms 540320 KB Output is correct
3 Correct 34 ms 13252 KB Output is correct
4 Correct 34 ms 13352 KB Output is correct
5 Correct 2379 ms 538964 KB Output is correct
6 Correct 10 ms 19032 KB Output is correct
7 Correct 1383 ms 148408 KB Output is correct
8 Correct 1361 ms 148616 KB Output is correct
9 Correct 36 ms 13256 KB Output is correct
10 Correct 485 ms 148040 KB Output is correct
11 Correct 481 ms 148824 KB Output is correct
12 Correct 498 ms 148548 KB Output is correct
13 Correct 523 ms 147720 KB Output is correct
14 Correct 5217 ms 1497324 KB Output is correct
15 Correct 5098 ms 1496760 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 224 ms 99156 KB Output is correct
18 Correct 1121 ms 523728 KB Output is correct
19 Correct 5131 ms 1496984 KB Output is correct
20 Correct 5145 ms 1496784 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 4967 ms 1423140 KB Output is correct
24 Correct 218 ms 96340 KB Output is correct
25 Correct 1095 ms 519308 KB Output is correct
26 Correct 8349 ms 1410396 KB Output is correct
27 Correct 8173 ms 1410436 KB Output is correct
28 Correct 34 ms 13308 KB Output is correct
29 Correct 4665 ms 1345092 KB Output is correct
30 Correct 5788 ms 1316064 KB Output is correct
31 Correct 1505 ms 719716 KB Output is correct
32 Correct 1720 ms 672460 KB Output is correct
33 Runtime error 9853 ms 2097152 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -