oj.uz

Submission #996434

# Submission time Handle Problem Language Result Execution time Memory
996434 2024-06-10T15:16:50 Z imarn Road Construction (JOI21_road_construction) C++14
32 / 100
 7068 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=3e5+5;
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 3276 ms 1074296 KB Output is correct
2 Correct 3096 ms 1074108 KB Output is correct
3 Correct 2956 ms 1031868 KB Output is correct
4 Correct 2509 ms 1031872 KB Output is correct
5 Correct 2916 ms 1073092 KB Output is correct
6 Correct 14 ms 15704 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 3504 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 2706 ms 1112876 KB Output is correct
2 Correct 2601 ms 1113280 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1297 ms 1111008 KB Output is correct
5 Correct 1681 ms 1112760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2706 ms 1112876 KB Output is correct
2 Correct 2601 ms 1113280 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1297 ms 1111008 KB Output is correct
5 Correct 1681 ms 1112760 KB Output is correct
6 Correct 2602 ms 1113376 KB Output is correct
7 Correct 2649 ms 1112248 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2645 ms 1112948 KB Output is correct
11 Correct 1357 ms 1111268 KB Output is correct
12 Correct 1663 ms 1112516 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3276 ms 1074296 KB Output is correct
2 Correct 3096 ms 1074108 KB Output is correct
3 Correct 2956 ms 1031868 KB Output is correct
4 Correct 2509 ms 1031872 KB Output is correct
5 Correct 2916 ms 1073092 KB Output is correct
6 Correct 14 ms 15704 KB Output is correct
7 Runtime error 7068 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 3276 ms 1074296 KB Output is correct
2 Correct 3096 ms 1074108 KB Output is correct
3 Correct 2956 ms 1031868 KB Output is correct
4 Correct 2509 ms 1031872 KB Output is correct
5 Correct 2916 ms 1073092 KB Output is correct
6 Correct 14 ms 15704 KB Output is correct
7 Runtime error 3504 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -