Submission #999237

#	Time	Username	Problem	Language	Result	Execution time	Memory
999237		8pete8	Road Construction (JOI21_road_construction)	C++17	100 / 100	3148 ms	1579452 KiB

road_construction

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mxn=2e5+5e4+10,inf=1e18,lg=30,mx=1e9,nx=-1e9,minf=-1e18,mod=998244353;
/*
find k cheapest road
we can get the cheapest road for i node with sparse seg?
persist sparse segtee ??TT
*/
int n,k;
struct node{
    pair<pii,pii> val;
    node*l,*r;
    node():val({{inf,inf},{inf,inf}}),l(0),r(0){};
};
map<int32_t,vector<int32_t>>mp;
map<int32_t,int32_t>cnt[mxn+10];
struct persist{
    node *root[mxn+10];
    pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val.f;}
    pii get2(node *x){return (x==NULL)?make_pair(inf,inf):x->val.s;}
    void update(int l,int r,node *last,node *&cur,int pos,int val,int val2){
        if(last==NULL)cur=new node();
        else cur=new node(*last);
        if(l==r){
            return void(cur->val={{val,pos},{val2,pos}});
        }
        int mid=l+(r-l)/2;
        if(pos<=mid)update(l,mid,((last==NULL)?last:last->l),cur->l,pos,val,val2);
        else update(mid+1,r,((last==NULL)?last:last->r),cur->r,pos,val,val2);
        cur->val.f=min(get(cur->l),get(cur->r));
        cur->val.s=min(get2(cur->l),get2(cur->r));
    }
    pii qry(int l,int r,node *cur,int ql,int qr,int mode){
        if(cur==NULL||l>qr||r<ql)return {inf,inf};
        if(ql<=l&&r<=qr){
            if(mode)return cur->val.s;
            return cur->val.f;
        }
        int mid=l+(r-l)/2;
        return min(qry(l,mid,cur->l,ql,qr,mode),qry(mid+1,r,cur->r,ql,qr,mode));
    }
}t,t2;
void show(){
    cout<<"PPPP\n";
}
int32_t main(){
    fastio
    cin>>n>>k;
    vector<pii>v(n);
    for(int i=0;i<n;i++)cin>>v[i].f>>v[i].s;
    sort(all(v));
    for(int i=0;i<n;i++)mp[v[i].s].pb(i);
    for(int i=1;i<n;i++){
        //update the last one
        t.update(nx,mx,t.root[i-(i!=0)],t.root[i],v[i-1].s,-v[i-1].f+v[i-1].s,-v[i-1].f-v[i-1].s);
    }
    auto del=[&](int x,int pos){
        if(cnt[x].find(pos)==cnt[x].end())cnt[x][pos]=upper_bound(all(mp[pos]),x-1)-mp[pos].begin()-1;
        cnt[x][pos]--;
        return ((cnt[x][pos]<0)?inf:v[mp[pos][cnt[x][pos]]].f);
    };
    auto get=[&](int x){
        pii a=t.qry(nx,mx,t.root[x],v[x].s,mx,0),b=t.qry(nx,mx,t.root[x],nx,v[x].s-1,1);
        int up;
        if(max(minf,a.f-v[x].s)<min(inf,b.f+v[x].s)){
            if(a.s==inf)return inf;
            up=del(x,a.s);
            if(up!=inf)t.update(nx,mx,t.root[x],t.root[x],a.s,-up+a.s,-up-a.s);
            else t.update(nx,mx,t.root[x],t.root[x],a.s,inf,inf);
            return v[x].f+a.f-v[x].s;
        }
        else{
            if(b.s==inf)return inf;
            up=del(x,b.s);
            if(up!=inf)t.update(nx,mx,t.root[x],t.root[x],b.s,-up+b.s,-up-b.s);
            else t.update(nx,mx,t.root[x],t.root[x],b.s,inf,inf);
            return v[x].f+b.f+v[x].s;
        }
    };
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int i=0;i<n;i++)pq.push({get(i),i});
    for(int i=0;i<k;i++){
        if(pq.empty())assert(0);
        cout<<pq.top().f<<"\n";
        int x=pq.top().s;
        pq.pop();
        pq.push({get(x),x});
    }
}
/*
3 3
-1 0
0 2
0 0

5 4 
1 -1 
2 0 
-1 0 
0 2 
0 -2

4 6 
0 0 
1 0 
3 0
4 0
*/

Compilation message (stderr)

road_construction.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
road_construction.cpp:45:10: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 |     node():val({{inf,inf},{inf,inf}}),l(0),r(0){};
      |          ^
road_construction.cpp:51:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 |     pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val.f;}
      |                    ^
road_construction.cpp:52:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 |     pii get2(node *x){return (x==NULL)?make_pair(inf,inf):x->val.s;}
      |                     ^
road_construction.cpp:53:75: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |     void update(int l,int r,node *last,node *&cur,int pos,int val,int val2){
      |                                                                           ^
road_construction.cpp:65:57: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 |     pii qry(int l,int r,node *cur,int ql,int qr,int mode){
      |                                                         ^
road_construction.cpp:75:11: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   75 | void show(){
      |           ^
road_construction.cpp:78:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   78 | int32_t main(){
      |              ^
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:89:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   89 |     auto del=[&](int x,int pos){
      |                               ^
road_construction.cpp:94:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   94 |     auto get=[&](int x){
      |                       ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35