oj.uz

Submission #996440

# Submission time Handle Problem Language Result Execution time Memory
996440 2024-06-10T15:30:29 Z imarn Road Construction (JOI21_road_construction) C++14
32 / 100
 7281 ms 2097152 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;
        pre[0][i]=update(pre[0][i],1,n,u.s.s,1e18);
        pre[1][i]=update(pre[1][i],1,n,u.s.s,1e18);
        suf[0][i]=update(suf[0][i],1,n,u.s.s,1e18);
        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 3144 ms 1074372 KB Output is correct
2 Correct 3150 ms 1074248 KB Output is correct
3 Correct 2974 ms 1031840 KB Output is correct
4 Correct 2574 ms 1031856 KB Output is correct
5 Correct 3018 ms 1073088 KB Output is correct
6 Correct 14 ms 15708 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 3596 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2731 ms 1104824 KB Output is correct
2 Correct 2764 ms 1104612 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1432 ms 1107688 KB Output is correct
5 Correct 1783 ms 1109964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2731 ms 1104824 KB Output is correct
2 Correct 2764 ms 1104612 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1432 ms 1107688 KB Output is correct
5 Correct 1783 ms 1109964 KB Output is correct
6 Correct 2788 ms 1109472 KB Output is correct
7 Correct 2734 ms 1110312 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2710 ms 1109412 KB Output is correct
11 Correct 1329 ms 1108928 KB Output is correct
12 Correct 1821 ms 1110284 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3144 ms 1074372 KB Output is correct
2 Correct 3150 ms 1074248 KB Output is correct
3 Correct 2974 ms 1031840 KB Output is correct
4 Correct 2574 ms 1031856 KB Output is correct
5 Correct 3018 ms 1073088 KB Output is correct
6 Correct 14 ms 15708 KB Output is correct
7 Runtime error 7281 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3144 ms 1074372 KB Output is correct
2 Correct 3150 ms 1074248 KB Output is correct
3 Correct 2974 ms 1031840 KB Output is correct
4 Correct 2574 ms 1031856 KB Output is correct
5 Correct 3018 ms 1073088 KB Output is correct
6 Correct 14 ms 15708 KB Output is correct
7 Runtime error 3596 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -