oj.uz

Submission #996443

# Submission time Handle Problem Language Result Execution time Memory
996443 2024-06-10T15:37:03 Z imarn Road Construction (JOI21_road_construction) C++14
100 / 100
 7469 ms 1589200 KB 
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=250005;
int id[mxn]{0},rev[mxn]{0};
struct node{
    pll v;
    node*l,*r;
    node(): v({1e18,-1}),l(NULL),r(NULL){};
    node(ll x,ll y) : v({x,y}),l(NULL),r(NULL){};
    node(node*l,node*r) : v(min(l->v,r->v)),l(l),r(r){};
};map<pll,bool>mp;
node*pre[2][mxn],*suf[2][mxn];
pll p[mxn];
pair<pll,int>y[mxn];
node* build(node*t,int l,int r){
    t=new node();
    if(l==r)return new node(1e18,l);
    int m=(l+r)>>1;
    return new node(build(t->l,l,m),build(t->r,m+1,r));
}
node *update(node*t,int l,int r,int id,ll v){
    if(l==r)return new node(v,id);
    int m=(l+r)>>1;
    if(id<=m)return new node(update(t->l,l,m,id,v),t->r);
    else return new node(t->l,update(t->r,m+1,r,id,v));
}
pll qr(node*t,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return {1e18,-1};
    if(r<=tr&&l>=tl)return t->v;
    int m=(l+r)>>1;
    return min(qr(t->l,l,m,tl,tr),qr(t->r,m+1,r,tl,tr));
}
bool cmp(pair<pll,ll>a,pair<pll,ll>b){
    if(a.f.s==b.f.s)return a<b;
    return a.f.s<b.f.s;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>p[i].f>>p[i].s,y[i].f=p[i],y[i].s=0;
    sort(y+1,y+n+1);for(int i=1;i<=n;i++)y[i].s=i;
    sort(y+1,y+n+1,cmp);for(int i=1;i<=n;i++)id[y[i].s]=i,rev[i]=y[i].s;
    sort(p+1,p+n+1);
    pre[0][1]=build(pre[0][1],1,n);
    pre[1][1]=build(pre[1][1],1,n);
    for(int i=2;i<=n;i++){
        pre[0][i]=update(pre[0][i-1],1,n,id[i-1],-p[i-1].f-p[i-1].s);
        pre[1][i]=update(pre[1][i-1],1,n,id[i-1],-p[i-1].f+p[i-1].s);
    }suf[0][n]=build(suf[0][n],1,n);suf[1][n]=build(suf[1][n],1,n);
    for(int i=n-1;i>=1;i--){
        suf[0][i]=update(suf[0][i+1],1,n,id[i+1],p[i+1].f-p[i+1].s);
        suf[1][i]=update(suf[1][i+1],1,n,id[i+1],p[i+1].f+p[i+1].s);
    }priority_queue<pair<ll,pll>,vector<pair<ll,pll>>,greater<pair<ll,pll>>>pq;
    for(int i=1;i<=n;i++){
        pll ans1 = qr(pre[0][i],1,n,1,id[i]);
        ans1.f+=p[i].f+p[i].s;
        pll ans2 = qr(pre[1][i],1,n,id[i],n);
        ans2.f+=p[i].f-p[i].s;
        pll ans3 = qr(suf[0][i],1,n,1,id[i]);
        ans3.f+=-p[i].f+p[i].s;
        pll ans4 = qr(suf[1][i],1,n,id[i],n);
        ans4.f+=-p[i].f-p[i].s;
        ll res=1e17;int mem=-1;
        if(res>ans1.f)res=ans1.f,mem=ans1.s;
        if(res>ans2.f)res=ans2.f,mem=ans2.s;
        if(res>ans3.f)res=ans3.f,mem=ans3.s;
        if(res>ans4.f)res=ans4.f,mem=ans4.s;
        pq.push({res,{i,mem}});
    }vector<ll>ans;ll cnt=k;
    while(cnt>0){
        auto u=pq.top();pq.pop();
        if(mp.find({u.s.f,rev[u.s.s]})==mp.end()){
            ans.pb(u.f);mp[{u.s.f,rev[u.s.s]}]=mp[{rev[u.s.s],u.s.f}]=1;cnt--;
        }
        int i=u.s.f;
        if(i>rev[u.s.s]&&id[i]>u.s.s)pre[0][i]=update(pre[0][i],1,n,u.s.s,1e18);
        if(i>rev[u.s.s]&&u.s.s>id[i])pre[1][i]=update(pre[1][i],1,n,u.s.s,1e18);
        if(i<rev[u.s.s]&&id[i]>u.s.s)suf[0][i]=update(suf[0][i],1,n,u.s.s,1e18);
        if(i<rev[u.s.s]&&id[i]<u.s.s)suf[1][i]=update(suf[1][i],1,n,u.s.s,1e18);
        pll ans1 = qr(pre[0][i],1,n,1,id[i]);ans1.f+=p[i].f+p[i].s;
        pll ans2 = qr(pre[1][i],1,n,id[i],n);ans2.f+=p[i].f-p[i].s;
        pll ans3 = qr(suf[0][i],1,n,1,id[i]);ans3.f+=-p[i].f+p[i].s;
        pll ans4 = qr(suf[1][i],1,n,id[i],n);ans4.f+=-p[i].f-p[i].s;
        ll res=1e17;int mem=-1;
        if(res>ans1.f)res=ans1.f,mem=ans1.s;
        if(res>ans2.f)res=ans2.f,mem=ans2.s;
        if(res>ans3.f)res=ans3.f,mem=ans3.s;
        if(res>ans4.f)res=ans4.f,mem=ans4.s;
        if(mem==-1)continue;
        pq.push({res,{i,mem}});
    }
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<'\n';
    }
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1590 ms 300996 KB Output is correct
2 Correct 1533 ms 300988 KB Output is correct
3 Correct 1391 ms 289696 KB Output is correct
4 Correct 1316 ms 289728 KB Output is correct
5 Correct 1479 ms 299712 KB Output is correct
6 Correct 7 ms 9560 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3853 ms 1583288 KB Output is correct
2 Correct 3678 ms 1585012 KB Output is correct
3 Correct 1206 ms 289472 KB Output is correct
4 Correct 2653 ms 1586104 KB Output is correct
5 Correct 2385 ms 1586104 KB Output is correct
6 Correct 2394 ms 1586360 KB Output is correct
7 Correct 2710 ms 1585668 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2660 ms 1105884 KB Output is correct
2 Correct 2637 ms 1104600 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1330 ms 1108064 KB Output is correct
5 Correct 1718 ms 1111304 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2660 ms 1105884 KB Output is correct
2 Correct 2637 ms 1104600 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1330 ms 1108064 KB Output is correct
5 Correct 1718 ms 1111304 KB Output is correct
6 Correct 2639 ms 1110900 KB Output is correct
7 Correct 2647 ms 1110984 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2651 ms 1110520 KB Output is correct
11 Correct 1406 ms 1107280 KB Output is correct
12 Correct 1703 ms 1111368 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1590 ms 300996 KB Output is correct
2 Correct 1533 ms 300988 KB Output is correct
3 Correct 1391 ms 289696 KB Output is correct
4 Correct 1316 ms 289728 KB Output is correct
5 Correct 1479 ms 299712 KB Output is correct
6 Correct 7 ms 9560 KB Output is correct
7 Correct 5408 ms 878328 KB Output is correct
8 Correct 5590 ms 878560 KB Output is correct
9 Correct 1349 ms 289728 KB Output is correct
10 Correct 2782 ms 877760 KB Output is correct
11 Correct 3490 ms 877260 KB Output is correct
12 Correct 1577 ms 877268 KB Output is correct
13 Correct 2073 ms 876840 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1590 ms 300996 KB Output is correct
2 Correct 1533 ms 300988 KB Output is correct
3 Correct 1391 ms 289696 KB Output is correct
4 Correct 1316 ms 289728 KB Output is correct
5 Correct 1479 ms 299712 KB Output is correct
6 Correct 7 ms 9560 KB Output is correct
7 Correct 3853 ms 1583288 KB Output is correct
8 Correct 3678 ms 1585012 KB Output is correct
9 Correct 1206 ms 289472 KB Output is correct
10 Correct 2653 ms 1586104 KB Output is correct
11 Correct 2385 ms 1586104 KB Output is correct
12 Correct 2394 ms 1586360 KB Output is correct
13 Correct 2710 ms 1585668 KB Output is correct
14 Correct 2660 ms 1105884 KB Output is correct
15 Correct 2637 ms 1104600 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1330 ms 1108064 KB Output is correct
18 Correct 1718 ms 1111304 KB Output is correct
19 Correct 2639 ms 1110900 KB Output is correct
20 Correct 2647 ms 1110984 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 2651 ms 1110520 KB Output is correct
24 Correct 1406 ms 1107280 KB Output is correct
25 Correct 1703 ms 1111368 KB Output is correct
26 Correct 5408 ms 878328 KB Output is correct
27 Correct 5590 ms 878560 KB Output is correct
28 Correct 1349 ms 289728 KB Output is correct
29 Correct 2782 ms 877760 KB Output is correct
30 Correct 3490 ms 877260 KB Output is correct
31 Correct 1577 ms 877268 KB Output is correct
32 Correct 2073 ms 876840 KB Output is correct
33 Correct 7469 ms 1589200 KB Output is correct
34 Correct 7330 ms 1589184 KB Output is correct
35 Correct 4432 ms 1588608 KB Output is correct
36 Correct 2627 ms 1587896 KB Output is correct
37 Correct 2674 ms 1587928 KB Output is correct
38 Correct 3447 ms 1587876 KB Output is correct