oj.uz

Submission #788051

# Submission time Handle Problem Language Result Execution time Memory
788051 2023-07-19T17:02:42 Z winter0101 Road Construction (JOI21_road_construction) C++14
65 / 100
 1719 ms 646000 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[20000009];
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

# Verdict Execution time Memory Grader output
1 Correct 300 ms 316068 KB Output is correct
2 Correct 260 ms 316108 KB Output is correct
3 Correct 268 ms 316108 KB Output is correct
4 Correct 233 ms 316128 KB Output is correct
5 Correct 265 ms 314964 KB Output is correct
6 Correct 106 ms 313528 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1026 ms 335132 KB Output is correct
2 Correct 1034 ms 338168 KB Output is correct
3 Correct 222 ms 316044 KB Output is correct
4 Correct 594 ms 338044 KB Output is correct
5 Correct 627 ms 338084 KB Output is correct
6 Correct 693 ms 338296 KB Output is correct
7 Correct 670 ms 337616 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1372 ms 350676 KB Output is correct
2 Correct 1315 ms 355692 KB Output is correct
3 Correct 107 ms 313440 KB Output is correct
4 Correct 428 ms 336864 KB Output is correct
5 Correct 664 ms 356004 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1372 ms 350676 KB Output is correct
2 Correct 1315 ms 355692 KB Output is correct
3 Correct 107 ms 313440 KB Output is correct
4 Correct 428 ms 336864 KB Output is correct
5 Correct 664 ms 356004 KB Output is correct
6 Correct 1380 ms 355692 KB Output is correct
7 Correct 1297 ms 355616 KB Output is correct
8 Correct 110 ms 313320 KB Output is correct
9 Correct 108 ms 313444 KB Output is correct
10 Correct 1355 ms 355676 KB Output is correct
11 Correct 423 ms 336812 KB Output is correct
12 Correct 689 ms 355880 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 316068 KB Output is correct
2 Correct 260 ms 316108 KB Output is correct
3 Correct 268 ms 316108 KB Output is correct
4 Correct 233 ms 316128 KB Output is correct
5 Correct 265 ms 314964 KB Output is correct
6 Correct 106 ms 313528 KB Output is correct
7 Correct 1259 ms 330256 KB Output is correct
8 Correct 1289 ms 330352 KB Output is correct
9 Correct 242 ms 316220 KB Output is correct
10 Correct 702 ms 329568 KB Output is correct
11 Correct 731 ms 329396 KB Output is correct
12 Correct 506 ms 330256 KB Output is correct
13 Correct 572 ms 328724 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 316068 KB Output is correct
2 Correct 260 ms 316108 KB Output is correct
3 Correct 268 ms 316108 KB Output is correct
4 Correct 233 ms 316128 KB Output is correct
5 Correct 265 ms 314964 KB Output is correct
6 Correct 106 ms 313528 KB Output is correct
7 Correct 1026 ms 335132 KB Output is correct
8 Correct 1034 ms 338168 KB Output is correct
9 Correct 222 ms 316044 KB Output is correct
10 Correct 594 ms 338044 KB Output is correct
11 Correct 627 ms 338084 KB Output is correct
12 Correct 693 ms 338296 KB Output is correct
13 Correct 670 ms 337616 KB Output is correct
14 Correct 1372 ms 350676 KB Output is correct
15 Correct 1315 ms 355692 KB Output is correct
16 Correct 107 ms 313440 KB Output is correct
17 Correct 428 ms 336864 KB Output is correct
18 Correct 664 ms 356004 KB Output is correct
19 Correct 1380 ms 355692 KB Output is correct
20 Correct 1297 ms 355616 KB Output is correct
21 Correct 110 ms 313320 KB Output is correct
22 Correct 108 ms 313444 KB Output is correct
23 Correct 1355 ms 355676 KB Output is correct
24 Correct 423 ms 336812 KB Output is correct
25 Correct 689 ms 355880 KB Output is correct
26 Correct 1259 ms 330256 KB Output is correct
27 Correct 1289 ms 330352 KB Output is correct
28 Correct 242 ms 316220 KB Output is correct
29 Correct 702 ms 329568 KB Output is correct
30 Correct 731 ms 329396 KB Output is correct
31 Correct 506 ms 330256 KB Output is correct
32 Correct 572 ms 328724 KB Output is correct
33 Runtime error 1719 ms 646000 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -