제출 #911360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911360		alexander707070	Road Construction (JOI21_road_construction)	C++14	100 / 100	2651 ms	630208 KiB

road_construction

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35