Submission #999167

#	Time	Username	Problem	Language	Result	Execution time	Memory
999167		8pete8	Road Construction (JOI21_road_construction)	C++17	27 / 100	2499 ms	2097152 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=3e5+5,inf=1e18,lg=30,mx=1e9,nx=-1e9,minf=-1e9,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{
    pii val;
    node*l,*r;
    node():val({inf,inf}),l(0),r(0){};
};
map<int,vector<int>>mp;
map<int,int>cnt[mxn+10];
struct persist{
    node *root[mxn+10];
    pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val;}
    void update(int l,int r,node *last,node *&cur,int pos,int val){
        if(last==NULL)cur=new node();
        else cur=new node(*last);
        if(l==r)return void(cur->val={val,pos});
        int mid=l+(r-l)/2;
        if(pos<=mid)update(l,mid,((last==NULL)?last:last->l),cur->l,pos,val);
        else update(mid+1,r,((last==NULL)?last:last->r),cur->r,pos,val);
        cur->val=min(get(cur->l),get(cur->r));
    }
    pii qry(int l,int r,node *cur,int ql,int qr){
        if(cur==NULL||l>qr||r<ql)return {inf,inf};
        if(ql<=l&&r<=qr)return cur->val;
        int mid=l+(r-l)/2;
        return min(qry(l,mid,cur->l,ql,qr),qry(mid+1,r,cur->r,ql,qr));
    }
}t,t2;
void show(){
    cout<<"PPPP\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<=0;j++)cout<<t.qry(nx,mx,t.root[i],j,j).f<<" ";
        cout<<'\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,t.root[i]=new node(),t2.root[i]=new node();
    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);
        t2.update(nx,mx,t2.root[i-(i!=0)],t2.root[i],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[cnt[x][pos]].f;
    };
    auto get=[&](int x){
        pii a=t.qry(nx,mx,t.root[x],v[x].s,mx),b=t2.qry(nx,mx,t2.root[x],nx,v[x].s-1);
        int up;
        if(a.f-v[x].s<b.f+v[x].s){
            up=del(x,a.s);
            if(up!=inf){
                t.update(nx,mx,t.root[x],t.root[x],a.s,-up+a.s);
                t2.update(nx,mx,t2.root[x],t2.root[x],a.s,-up-a.s);
            }
            else t.update(nx,mx,t.root[x],t.root[x],a.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],a.s,inf);
            return v[x].f+a.f-v[x].s;
        }
        else{
            up=del(x,b.s);
            if(up!=inf){
                t.update(nx,mx,t.root[x],t.root[x],b.s,-up+b.s);
                t2.update(nx,mx,t2.root[x],t2.root[x],b.s,-up-b.s);
            }
            else t.update(nx,mx,t.root[x],t.root[x],b.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],b.s,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}),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;}
      |                    ^
road_construction.cpp:52:66: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 |     void update(int l,int r,node *last,node *&cur,int pos,int val){
      |                                                                  ^
road_construction.cpp:61:48: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 |     pii qry(int l,int r,node *cur,int ql,int qr){
      |                                                ^
road_construction.cpp:68:11: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 | void show(){
      |           ^
road_construction.cpp:75:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   75 | int32_t main(){
      |              ^
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:87:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   87 |     auto del=[&](int x,int pos){
      |                               ^
road_construction.cpp:92:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   92 |     auto get=[&](int x){
      |                       ^

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