oj.uz

Submission #788054

# Submission time Handle Problem Language Result Execution time Memory
788054 2023-07-19T17:05:09 Z winter0101 Road Construction (JOI21_road_construction) C++14
100 / 100
 2302 ms 509264 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=sml;
    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 401 ms 472608 KB Output is correct
2 Correct 340 ms 472652 KB Output is correct
3 Correct 317 ms 472776 KB Output is correct
4 Correct 304 ms 472788 KB Output is correct
5 Correct 336 ms 471608 KB Output is correct
6 Correct 164 ms 470052 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 491788 KB Output is correct
2 Correct 1064 ms 491664 KB Output is correct
3 Correct 306 ms 472596 KB Output is correct
4 Correct 654 ms 491448 KB Output is correct
5 Correct 703 ms 491788 KB Output is correct
6 Correct 691 ms 491760 KB Output is correct
7 Correct 752 ms 490936 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1331 ms 507148 KB Output is correct
2 Correct 1372 ms 507084 KB Output is correct
3 Correct 162 ms 470060 KB Output is correct
4 Correct 479 ms 490536 KB Output is correct
5 Correct 736 ms 507028 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1331 ms 507148 KB Output is correct
2 Correct 1372 ms 507084 KB Output is correct
3 Correct 162 ms 470060 KB Output is correct
4 Correct 479 ms 490536 KB Output is correct
5 Correct 736 ms 507028 KB Output is correct
6 Correct 1515 ms 507068 KB Output is correct
7 Correct 1306 ms 507156 KB Output is correct
8 Correct 179 ms 470044 KB Output is correct
9 Correct 169 ms 470052 KB Output is correct
10 Correct 1336 ms 507076 KB Output is correct
11 Correct 487 ms 490508 KB Output is correct
12 Correct 705 ms 507116 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 472608 KB Output is correct
2 Correct 340 ms 472652 KB Output is correct
3 Correct 317 ms 472776 KB Output is correct
4 Correct 304 ms 472788 KB Output is correct
5 Correct 336 ms 471608 KB Output is correct
6 Correct 164 ms 470052 KB Output is correct
7 Correct 1304 ms 486864 KB Output is correct
8 Correct 1316 ms 486840 KB Output is correct
9 Correct 299 ms 472664 KB Output is correct
10 Correct 773 ms 486180 KB Output is correct
11 Correct 800 ms 485984 KB Output is correct
12 Correct 540 ms 486756 KB Output is correct
13 Correct 624 ms 485356 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 472608 KB Output is correct
2 Correct 340 ms 472652 KB Output is correct
3 Correct 317 ms 472776 KB Output is correct
4 Correct 304 ms 472788 KB Output is correct
5 Correct 336 ms 471608 KB Output is correct
6 Correct 164 ms 470052 KB Output is correct
7 Correct 1139 ms 491788 KB Output is correct
8 Correct 1064 ms 491664 KB Output is correct
9 Correct 306 ms 472596 KB Output is correct
10 Correct 654 ms 491448 KB Output is correct
11 Correct 703 ms 491788 KB Output is correct
12 Correct 691 ms 491760 KB Output is correct
13 Correct 752 ms 490936 KB Output is correct
14 Correct 1331 ms 507148 KB Output is correct
15 Correct 1372 ms 507084 KB Output is correct
16 Correct 162 ms 470060 KB Output is correct
17 Correct 479 ms 490536 KB Output is correct
18 Correct 736 ms 507028 KB Output is correct
19 Correct 1515 ms 507068 KB Output is correct
20 Correct 1306 ms 507156 KB Output is correct
21 Correct 179 ms 470044 KB Output is correct
22 Correct 169 ms 470052 KB Output is correct
23 Correct 1336 ms 507076 KB Output is correct
24 Correct 487 ms 490508 KB Output is correct
25 Correct 705 ms 507116 KB Output is correct
26 Correct 1304 ms 486864 KB Output is correct
27 Correct 1316 ms 486840 KB Output is correct
28 Correct 299 ms 472664 KB Output is correct
29 Correct 773 ms 486180 KB Output is correct
30 Correct 800 ms 485984 KB Output is correct
31 Correct 540 ms 486756 KB Output is correct
32 Correct 624 ms 485356 KB Output is correct
33 Correct 2302 ms 509264 KB Output is correct
34 Correct 2275 ms 509108 KB Output is correct
35 Correct 1407 ms 508368 KB Output is correct
36 Correct 949 ms 508760 KB Output is correct
37 Correct 895 ms 509072 KB Output is correct
38 Correct 1020 ms 507520 KB Output is correct