oj.uz

Submission #788053

# Submission time Handle Problem Language Result Execution time Memory
788053 2023-07-19T17:04:30 Z winter0101 Road Construction (JOI21_road_construction) C++14
100 / 100
 2307 ms 514208 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[30000009];
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 329 ms 472712 KB Output is correct
2 Correct 324 ms 472636 KB Output is correct
3 Correct 310 ms 472692 KB Output is correct
4 Correct 288 ms 472672 KB Output is correct
5 Correct 310 ms 471580 KB Output is correct
6 Correct 163 ms 470076 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 491728 KB Output is correct
2 Correct 1189 ms 494720 KB Output is correct
3 Correct 271 ms 472540 KB Output is correct
4 Correct 671 ms 494452 KB Output is correct
5 Correct 693 ms 494648 KB Output is correct
6 Correct 707 ms 494788 KB Output is correct
7 Correct 718 ms 494132 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1397 ms 507196 KB Output is correct
2 Correct 1359 ms 512216 KB Output is correct
3 Correct 163 ms 469964 KB Output is correct
4 Correct 478 ms 493408 KB Output is correct
5 Correct 717 ms 512440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1397 ms 507196 KB Output is correct
2 Correct 1359 ms 512216 KB Output is correct
3 Correct 163 ms 469964 KB Output is correct
4 Correct 478 ms 493408 KB Output is correct
5 Correct 717 ms 512440 KB Output is correct
6 Correct 1375 ms 512208 KB Output is correct
7 Correct 1348 ms 512176 KB Output is correct
8 Correct 180 ms 469996 KB Output is correct
9 Correct 163 ms 469884 KB Output is correct
10 Correct 1366 ms 512160 KB Output is correct
11 Correct 487 ms 493476 KB Output is correct
12 Correct 989 ms 512372 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 472712 KB Output is correct
2 Correct 324 ms 472636 KB Output is correct
3 Correct 310 ms 472692 KB Output is correct
4 Correct 288 ms 472672 KB Output is correct
5 Correct 310 ms 471580 KB Output is correct
6 Correct 163 ms 470076 KB Output is correct
7 Correct 1332 ms 486804 KB Output is correct
8 Correct 1294 ms 486888 KB Output is correct
9 Correct 301 ms 472688 KB Output is correct
10 Correct 694 ms 486084 KB Output is correct
11 Correct 765 ms 485944 KB Output is correct
12 Correct 549 ms 486752 KB Output is correct
13 Correct 666 ms 485384 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 472712 KB Output is correct
2 Correct 324 ms 472636 KB Output is correct
3 Correct 310 ms 472692 KB Output is correct
4 Correct 288 ms 472672 KB Output is correct
5 Correct 310 ms 471580 KB Output is correct
6 Correct 163 ms 470076 KB Output is correct
7 Correct 1095 ms 491728 KB Output is correct
8 Correct 1189 ms 494720 KB Output is correct
9 Correct 271 ms 472540 KB Output is correct
10 Correct 671 ms 494452 KB Output is correct
11 Correct 693 ms 494648 KB Output is correct
12 Correct 707 ms 494788 KB Output is correct
13 Correct 718 ms 494132 KB Output is correct
14 Correct 1397 ms 507196 KB Output is correct
15 Correct 1359 ms 512216 KB Output is correct
16 Correct 163 ms 469964 KB Output is correct
17 Correct 478 ms 493408 KB Output is correct
18 Correct 717 ms 512440 KB Output is correct
19 Correct 1375 ms 512208 KB Output is correct
20 Correct 1348 ms 512176 KB Output is correct
21 Correct 180 ms 469996 KB Output is correct
22 Correct 163 ms 469884 KB Output is correct
23 Correct 1366 ms 512160 KB Output is correct
24 Correct 487 ms 493476 KB Output is correct
25 Correct 989 ms 512372 KB Output is correct
26 Correct 1332 ms 486804 KB Output is correct
27 Correct 1294 ms 486888 KB Output is correct
28 Correct 301 ms 472688 KB Output is correct
29 Correct 694 ms 486084 KB Output is correct
30 Correct 765 ms 485944 KB Output is correct
31 Correct 549 ms 486752 KB Output is correct
32 Correct 666 ms 485384 KB Output is correct
33 Correct 2307 ms 514160 KB Output is correct
34 Correct 2275 ms 514208 KB Output is correct
35 Correct 1407 ms 513572 KB Output is correct
36 Correct 978 ms 514188 KB Output is correct
37 Correct 900 ms 514176 KB Output is correct
38 Correct 1077 ms 512944 KB Output is correct