oj.uz

Submission #911360

# Submission time Handle Problem Language Result Execution time Memory
911360 2024-01-18T20:19:58 Z alexander707070 Road Construction (JOI21_road_construction) C++14
100 / 100
 2651 ms 630208 KB 
#include<bits/stdc++.h>
#define MAXN 250007
using namespace std;

const long long inf=1e15;

struct point{
    long long x,y;
};

bool cmp(point fr,point sc){
    return fr.x<sc.x;
}

struct node{
    int l,r;
    pair<long long,int> val;
};

node tree[100*MAXN];

int n,cnt,num,k,zero;
point p[MAXN];

vector< pair<long long,int> > w;
map< pair<long long,int> ,int> mp;
pair<long long,int> ret[MAXN];

priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > q;
pair<long long,int> c;

int root[MAXN][2];
/// left <= >
/// right <= >

void add_node(int l,int r){
    num++; 
    tree[num].l=l;
    tree[num].r=r;
}

pair<long long,int> combine(pair<long long,int> fr,pair<long long,int> sc){
    if(fr.first<sc.first)return fr;
    return sc;
}

pair<long long,int> getmin(int v,int l,int r,int ll,int rr){
    //cout<<v<<" "<<l<<" "<<r<<"\n";
    if(ll>rr or v==0)return {inf,0};

    if(l==ll and r==rr){
        return tree[v].val;
    }else{
        int tt=(l+r)/2;
        return combine( getmin(tree[v].l,l,tt,ll,min(tt,rr)) , getmin(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
    }
}

int update(int v,int l,int r,int pos,long long val){
    //cout<<v<<" "<<l<<" "<<r<<"\n";
    if(l==r){
        add_node(0,0);
        tree[num].val={val,l};
        return num;
    }else{
        int tt=(l+r)/2;

        int id;
        if(pos<=tt){
            id=update(tree[v].l,l,tt,pos,val);
            add_node(id,tree[v].r);
        }else{
            id=update(tree[v].r,tt+1,r,pos,val);
            add_node(tree[v].l,id);
        }

        tree[num].val=combine( tree[tree[num].l].val , tree[tree[num].r].val );
        return num;
    }
}

long long mins(int pos){
    long long ls=getmin(root[pos][0],1,cnt,1,p[pos].y).first;
    long long lg=getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).first;

    ls+=p[pos].x+ret[p[pos].y].first;
    lg+=p[pos].x-ret[p[pos].y].first;

    return min(ls,lg);
}

void erasemin(int pos){
    long long curr=mins(pos),ps=0;

    if(curr == getmin(root[pos][0],1,cnt,1,p[pos].y).first + p[pos].x + ret[p[pos].y].first ){
        ps=getmin(root[pos][0],1,cnt,1,p[pos].y).second;
        root[pos][0]=update(root[pos][0],1,cnt,ps,inf);
        return;
    }

    if(curr == getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).first + p[pos].x - ret[p[pos].y].first ){
        ps=getmin(root[pos][1],1,cnt,p[pos].y+1,cnt).second;
        root[pos][1]=update(root[pos][1],1,cnt,ps,inf);
        return;
    }
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
        w.push_back({p[i].y,i});
    }

    sort(w.begin(),w.end()); cnt=1;
    for(int i=0;i<w.size();i++){
        if(i>0 and w[i]!=w[i-1])cnt++;
        mp[w[i]]=cnt; ret[cnt]=w[i];
    }

    for(int i=1;i<=n;i++){
        p[i].y=mp[{p[i].y,i}];
    }

    sort(p+1,p+n+1,cmp);

    for(int i=1;i<=cnt;i++){
        zero=update(zero,1,cnt,i,inf);
    }
    root[0][0]=root[0][1]=zero;

    for(int i=1;i<=n;i++){
        root[i][0]=update(root[i-1][0],1,cnt,p[i].y,-p[i].x-ret[p[i].y].first);
        root[i][1]=update(root[i-1][1],1,cnt,p[i].y,-p[i].x+ret[p[i].y].first);
    }

    for(int i=1;i<=n;i++){
        erasemin(i);
        q.push({mins(i),i});
    }

    for(int i=1;i<=k;i++){
        c=q.top(); q.pop();

        erasemin(c.second);
        q.push({mins(c.second),c.second});

        cout<<c.first<<"\n";
    }

    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 595524 KB Output is correct
2 Correct 398 ms 595792 KB Output is correct
3 Correct 367 ms 595796 KB Output is correct
4 Correct 348 ms 595744 KB Output is correct
5 Correct 374 ms 594848 KB Output is correct
6 Correct 89 ms 592972 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2467 ms 625080 KB Output is correct
2 Correct 2584 ms 626288 KB Output is correct
3 Correct 359 ms 595672 KB Output is correct
4 Correct 1827 ms 626588 KB Output is correct
5 Correct 1971 ms 627220 KB Output is correct
6 Correct 2063 ms 626620 KB Output is correct
7 Correct 2139 ms 627388 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1353 ms 623556 KB Output is correct
2 Correct 1338 ms 628720 KB Output is correct
3 Correct 87 ms 592892 KB Output is correct
4 Correct 1195 ms 627744 KB Output is correct
5 Correct 1325 ms 629460 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1353 ms 623556 KB Output is correct
2 Correct 1338 ms 628720 KB Output is correct
3 Correct 87 ms 592892 KB Output is correct
4 Correct 1195 ms 627744 KB Output is correct
5 Correct 1325 ms 629460 KB Output is correct
6 Correct 1354 ms 628624 KB Output is correct
7 Correct 1442 ms 628832 KB Output is correct
8 Correct 88 ms 592820 KB Output is correct
9 Correct 88 ms 593044 KB Output is correct
10 Correct 1358 ms 628892 KB Output is correct
11 Correct 1340 ms 627252 KB Output is correct
12 Correct 1346 ms 628416 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 595524 KB Output is correct
2 Correct 398 ms 595792 KB Output is correct
3 Correct 367 ms 595796 KB Output is correct
4 Correct 348 ms 595744 KB Output is correct
5 Correct 374 ms 594848 KB Output is correct
6 Correct 89 ms 592972 KB Output is correct
7 Correct 1588 ms 610900 KB Output is correct
8 Correct 1535 ms 610736 KB Output is correct
9 Correct 347 ms 595656 KB Output is correct
10 Correct 908 ms 610104 KB Output is correct
11 Correct 1138 ms 610188 KB Output is correct
12 Correct 860 ms 610628 KB Output is correct
13 Correct 1162 ms 610372 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 595524 KB Output is correct
2 Correct 398 ms 595792 KB Output is correct
3 Correct 367 ms 595796 KB Output is correct
4 Correct 348 ms 595744 KB Output is correct
5 Correct 374 ms 594848 KB Output is correct
6 Correct 89 ms 592972 KB Output is correct
7 Correct 2467 ms 625080 KB Output is correct
8 Correct 2584 ms 626288 KB Output is correct
9 Correct 359 ms 595672 KB Output is correct
10 Correct 1827 ms 626588 KB Output is correct
11 Correct 1971 ms 627220 KB Output is correct
12 Correct 2063 ms 626620 KB Output is correct
13 Correct 2139 ms 627388 KB Output is correct
14 Correct 1353 ms 623556 KB Output is correct
15 Correct 1338 ms 628720 KB Output is correct
16 Correct 87 ms 592892 KB Output is correct
17 Correct 1195 ms 627744 KB Output is correct
18 Correct 1325 ms 629460 KB Output is correct
19 Correct 1354 ms 628624 KB Output is correct
20 Correct 1442 ms 628832 KB Output is correct
21 Correct 88 ms 592820 KB Output is correct
22 Correct 88 ms 593044 KB Output is correct
23 Correct 1358 ms 628892 KB Output is correct
24 Correct 1340 ms 627252 KB Output is correct
25 Correct 1346 ms 628416 KB Output is correct
26 Correct 1588 ms 610900 KB Output is correct
27 Correct 1535 ms 610736 KB Output is correct
28 Correct 347 ms 595656 KB Output is correct
29 Correct 908 ms 610104 KB Output is correct
30 Correct 1138 ms 610188 KB Output is correct
31 Correct 860 ms 610628 KB Output is correct
32 Correct 1162 ms 610372 KB Output is correct
33 Correct 2534 ms 628928 KB Output is correct
34 Correct 2651 ms 629396 KB Output is correct
35 Correct 1792 ms 629424 KB Output is correct
36 Correct 1746 ms 628676 KB Output is correct
37 Correct 1681 ms 630208 KB Output is correct
38 Correct 2128 ms 629368 KB Output is correct