oj.uz

답안 #788050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788050 2023-07-19T17:00:34 Z winter0101 Road Construction (JOI21_road_construction) C++14
32 / 100
 1356 ms 534560 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+5e4+9;
const int inf=2e9+1;
struct node {
int l,r;
pii val;
node(){
val.fi=inf;
val.se=0;
}
}st[15000009];
int rev[maxn];
pii combine(const pii &p, const pii &q){
if (p.fi<q.fi)return p;
return q;
}
int nnode=0;
int build(int l,int r){
int newnode=++nnode;
st[newnode].val.se=l;
if (l==r)return newnode;
int mid=(l+r)/2;
st[newnode].l=build(l,mid);
st[newnode].r=build(mid+1,r);
return newnode;
}
int copy(int id){
    st[++nnode]=st[id];
    return nnode;
}
int update(int id,int l,int r,int u,int val){
if (l>u||r<u)return id;
if (l==r){
    int newnode=copy(id);
    st[newnode].val.fi=val;
    st[newnode].val.se=rev[l];
    return newnode;
}
int newnode=copy(id);
int mid=(l+r)/2;
st[newnode].l=update(st[id].l,l,mid,u,val);
st[newnode].r=update(st[id].r,mid+1,r,u,val);
st[newnode].val=combine(st[st[newnode].l].val,st[st[newnode].r].val);
return newnode;
}
pii get(int id,int l,int r,int u,int v){
 if (l>v||r<u||u>v)return node().val;
 if (u<=l&&r<=v)return st[id].val;
 int mid=(l+r)/2;
 return combine(get(st[id].l,l,mid,u,v),get(st[id].r,mid+1,r,u,v));
}
pii a[maxn];
int n,k;
vector<int>posy;
vector<int> posfory(){
vector<pii>b;
b.resize(n+1);
for1(i,1,n){
b[i].se=i;
b[i].fi=a[i].se;
//cout<<a[i].se<<" "<<i<<'\n';
}
sort(b.begin()+1,b.end());
vector<int>sorting;
sorting.resize(n+1);
for1(i,1,n){
//cout<<b[i].fi<<" "<<b[i].se<<'\n';
sorting[b[i].se]=i;
rev[i]=b[i].se;
}
return sorting;
}
struct edg{
int u,v;
long long val;
bool operator < (const edg &p)const {
if (val==p.val&&u!=p.u)return u<p.u;
if (val==p.val&&u==p.u)return v<p.v;
return val<p.val;
}
};
int c[maxn],d[maxn];
//c for smaller
//d for greater
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>k;
    for1(i,1,n){
    cin>>a[i].fi>>a[i].se;
    }
    sort(a+1,a+1+n);
    posy=posfory();
    //for1(i,1,n)cout<<posy[i]<<" "<<rev[posy[i]]<<'\n';
    //for1(i,1,n)cout<<a[i].fi<<' '<<a[i].se<<'\n';
    //return 0;
    multiset<edg>choose;
    int sml=build(1,n),grt=build(1,n);
    for1(i,1,n){
    if (i==1){
    sml=update(sml,1,n,posy[i],-a[i].fi-a[i].se);
    grt=update(grt,1,n,posy[i],-a[i].fi+a[i].se);
    }
    else {
    //choose xi>xj yi>yj
    auto v=get(sml,1,n,1,posy[i]-1);
    //cout<<v.fi<<" "<<v.se<<'\n';
    if (v.fi<inf){
        choose.insert({i,v.se,1ll*v.fi+a[i].fi+a[i].se});
        c[i]=update(sml,1,n,posy[v.se],inf);
    }
    //end
    //choose xi>xj yi<yj
    auto u=get(grt,1,n,posy[i]+1,n);
    if (u.fi<inf){
        choose.insert({i,u.se,1ll*u.fi+a[i].fi-a[i].se});
        d[i]=update(grt,1,n,posy[u.se],inf);
    }
    //cout<<i<<" "<<u.se<<" "<<v.se<<" "<<u.fi<<" "<<v.fi<<'\n';
    //end
    sml=update(sml,1,n,posy[i],-a[i].fi-a[i].se);
    grt=update(grt,1,n,posy[i],-a[i].fi+a[i].se);
    }
    }
    //cout<<sz(choose)<<'\n';
    //for (auto u:choose)cout<<u.u<<" "<<u.v<<" "<<u.val<<'\n';
    for1(i,1,k){
    auto best=*(choose.begin());
    choose.erase(choose.begin());
    //cerr<<best.u<<" "<<best.v<<" "<<best.val<<'\n';
    cout<<best.val<<'\n';
    /*long long ans;
    cin>>ans;
    if (ans!=best.val){
        cout<<ans<<" "<<best.val<<" "<<i<<'\n';
        return 0;
    }*/
    int u=best.u,v=best.v;
    if (a[u].se<a[v].se){
        //grt
        auto newv=get(d[u],1,n,posy[u]+1,n);
        if (newv.fi>=inf)continue;
        choose.insert({u,newv.se,1ll*newv.fi+a[u].fi-a[u].se});
        d[u]=update(d[u],1,n,posy[newv.se],inf);
    }
    else {
        //sml
        auto newv=get(c[u],1,n,1,posy[u]-1);
        if (newv.fi>=inf)continue;
        choose.insert({u,newv.se,1ll*newv.fi+a[u].fi+a[u].se});
        c[u]=update(c[u],1,n,posy[newv.se],inf);
    }
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 237876 KB Output is correct
2 Correct 246 ms 237880 KB Output is correct
3 Correct 224 ms 237892 KB Output is correct
4 Correct 219 ms 237892 KB Output is correct
5 Correct 230 ms 236720 KB Output is correct
6 Correct 81 ms 235308 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 696 ms 518452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1098 ms 534560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1098 ms 534560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 237876 KB Output is correct
2 Correct 246 ms 237880 KB Output is correct
3 Correct 224 ms 237892 KB Output is correct
4 Correct 219 ms 237892 KB Output is correct
5 Correct 230 ms 236720 KB Output is correct
6 Correct 81 ms 235308 KB Output is correct
7 Correct 1356 ms 254096 KB Output is correct
8 Correct 1291 ms 254084 KB Output is correct
9 Correct 214 ms 237944 KB Output is correct
10 Correct 626 ms 253340 KB Output is correct
11 Correct 688 ms 253168 KB Output is correct
12 Correct 460 ms 253952 KB Output is correct
13 Correct 548 ms 252536 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 237876 KB Output is correct
2 Correct 246 ms 237880 KB Output is correct
3 Correct 224 ms 237892 KB Output is correct
4 Correct 219 ms 237892 KB Output is correct
5 Correct 230 ms 236720 KB Output is correct
6 Correct 81 ms 235308 KB Output is correct
7 Runtime error 696 ms 518452 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -