oj.uz

Submission #1109995

# Submission time Handle Problem Language Result Execution time Memory
1109995 2024-11-08T11:46:28 Z tosivanmak Road Construction (JOI21_road_construction) C++17
59 / 100
 1370 ms 706108 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

struct Persist{
    int seg[8000000],lc[8000000],rc[8000000];
    ll ptr=1;
    ll build(ll l, ll r){
        if(l==r){
            seg[ptr]=1e18,lc[ptr]=rc[ptr]=-1; ptr++; return ptr-1;
        }
        else{
            ll mid=(l+r)>>1;
            ll curptr=ptr; ptr++;
            lc[curptr]=build(l,mid); rc[curptr]=build(mid+1,r);
            seg[curptr]=1e18;
            return curptr;
        }
    }
    ll upd(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[ptr]=val; lc[ptr]=rc[ptr]=-1; ptr++; return ptr-1;
        }
        else{
            ll mid=(l+r)>>1;
            ll curp=ptr; ptr++;
            if(ul<=mid){
                lc[curp]=upd(ul,l,mid,val,lc[id]); rc[curp]=rc[id];
            }
            else{
                rc[curp]=upd(ul,mid+1,r,val,rc[id]); lc[curp]=lc[id];
            }
            seg[curp]=min(seg[lc[curp]],seg[rc[curp]]);
            return curp;
        }
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll id){
        if(ql>qr)return 1e18;
        if(l>qr||r<ql)return 1e18;
        if(l>=ql&&r<=qr){
            return seg[id];
        }
        ll mid=(l+r)>>1;
        return min(qry(ql,qr,l,mid,lc[id]),qry(ql,qr,mid+1,r,rc[id]));
    }
    ll bs(ll l, ll r, ll k, ll id){
        if(l==r)return l;
        ll mid=(l+r)>>1;
        if(seg[lc[id]]==k)return bs(l,mid,k,lc[id]);
        return bs(mid+1,r,k,rc[id]);
    }
    ll find(ll ql, ll qr, ll l, ll r, ll id, ll k){
        if(ql>qr)return -1;
        if(l>qr||r<ql)return -1;
        if(l>=ql&&r<=qr){
            if(seg[id]!=k) return -1;
            return bs(l,r,k,id);
        }
        ll mid=(l+r)>>1;
        ll bruh=find(ql,qr,l,mid,lc[id],k);
        if(bruh!=-1)return bruh;
        bruh=find(ql,qr,mid+1,r,rc[id],k);
        return bruh;
    }
}st,st2;
struct THING{
    ll val,verx,very,insegpos;
    bool operator<(const THING& th)const{
        return val>th.val;
    }
};
priority_queue<THING>pq;
int version[250005][3];
int prevver,prevver2;
vector<pair<ll,ll> >disc;
ll pos(pair<ll,ll>x){
    return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;
}
int32_t main(){
    ll n,k;
    cin>>n>>k;
    ll x[n+5],y[n+5];
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    vector<pair<ll,ll> >pts;
    for(int i=1;i<=n;i++)pts.push_back({x[i],y[i]});
    sort(pts.begin(),pts.end());
    for(int i=0;i<pts.size();i++){
        disc.push_back({pts[i].second,i});
    }
    sort(disc.begin(),disc.end());
    prevver=st.build(1,disc.size()); prevver2=st2.build(1,disc.size());
    for(int i=0;i<pts.size();i++){
        int xx=pts[i].first,yy=pts[i].second;
        version[i][1]=prevver; version[i][2]=prevver2;
        prevver=st.upd(pos(make_pair(yy,i)),1,disc.size(),-xx-yy,prevver);
        prevver2=st2.upd(pos(make_pair(yy,i)),1,disc.size(),-xx+yy,prevver2);
    }
    for(int i=0;i<pts.size();i++){
        int xx=pts[i].first,yy=pts[i].second;
        ll posi=pos(make_pair(yy,i));
        ll for1=st.qry(1,posi,1,disc.size(),version[i][1]);
        ll segtreebst=st.find(1,posi,1,disc.size(),version[i][1],for1);
        pq.push({for1+xx+yy,i,1,segtreebst});
        ll for2=st2.qry(posi+1,disc.size(),1,disc.size(),version[i][2]);
        segtreebst=st2.find(posi+1,disc.size(),1,disc.size(),version[i][2],for2);
        pq.push({for2+xx-yy,i,2,segtreebst});
    }
    for(int i=1;i<=k;i++){
        THING lol=pq.top();
        ll val=lol.val,verx=lol.verx,very=lol.very,insegpos=lol.insegpos;
        ll xx=pts[verx].first,yy=pts[verx].second;
        pq.pop();
        cout<<val<<'\n';
        ll posi=pos(make_pair(yy,verx));
        if(very==1){
            version[verx][very]=st.upd(insegpos,1,disc.size(),1e18,version[verx][very]);
            ll for1=st.qry(1,posi,1,disc.size(),version[verx][1]);
            ll segtreebst=st.find(1,posi,1,disc.size(),version[verx][1],for1);
            pq.push({for1+xx+yy,verx,1,segtreebst});
        }
        else{
            version[verx][very]=st2.upd(insegpos,1,disc.size(),1e18,version[verx][very]);
            ll for2=st2.qry(posi+1,disc.size(),1,disc.size(),version[verx][2]);
            ll segtreebst=st2.find(posi+1,disc.size(),1,disc.size(),version[verx][2],for2);
            pq.push({for2+xx-yy,verx,2,segtreebst});
        }
    }
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 83204 KB Output is correct
2 Correct 216 ms 83072 KB Output is correct
3 Correct 202 ms 79176 KB Output is correct
4 Correct 171 ms 77136 KB Output is correct
5 Correct 188 ms 81992 KB Output is correct
6 Correct 5 ms 12880 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1242 ms 706108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1269 ms 286360 KB Output is correct
2 Correct 1306 ms 286484 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 388 ms 286276 KB Output is correct
5 Correct 741 ms 286284 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1269 ms 286360 KB Output is correct
2 Correct 1306 ms 286484 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 388 ms 286276 KB Output is correct
5 Correct 741 ms 286284 KB Output is correct
6 Correct 1335 ms 286484 KB Output is correct
7 Correct 1251 ms 286468 KB Output is correct
8 Correct 2 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 1265 ms 291592 KB Output is correct
11 Correct 401 ms 289432 KB Output is correct
12 Correct 712 ms 293708 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 83204 KB Output is correct
2 Correct 216 ms 83072 KB Output is correct
3 Correct 202 ms 79176 KB Output is correct
4 Correct 171 ms 77136 KB Output is correct
5 Correct 188 ms 81992 KB Output is correct
6 Correct 5 ms 12880 KB Output is correct
7 Correct 1370 ms 227496 KB Output is correct
8 Correct 1306 ms 225964 KB Output is correct
9 Correct 169 ms 77176 KB Output is correct
10 Correct 716 ms 225440 KB Output is correct
11 Correct 831 ms 225256 KB Output is correct
12 Correct 559 ms 226344 KB Output is correct
13 Correct 663 ms 224608 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 83204 KB Output is correct
2 Correct 216 ms 83072 KB Output is correct
3 Correct 202 ms 79176 KB Output is correct
4 Correct 171 ms 77136 KB Output is correct
5 Correct 188 ms 81992 KB Output is correct
6 Correct 5 ms 12880 KB Output is correct
7 Runtime error 1242 ms 706108 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -