Submission #1158433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158433		timoni	Road Construction (JOI21_road_construction)	C++17	39 / 100	1148 ms	540660 KiB

road_construction

// made by Tima
// 2025 will be a golden year...
//BREAK YOUR LIMITS!!!!
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define int long long
#define F first
#define S second
#define y1 SBIL
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define tpii pair <pair <int,int> , int>
using namespace std;
using namespace __gnu_pbds;
const int N = 3e5 + 5 , M = 5e5 + 5;
int mod = 1e9 + 7;
const int INF = 1e18;
int n,k,x[N],y[N],root[M],y1[N],val[3][N],timer;
pii p[N];
tpii br[N];
struct node{
	int x,i,l,r;
}t[200 * N];
void build(int &v , int tl = 1 , int tr = n){
	if(!v) v = ++ timer;
	if(tl == tr){
		t[v].x = INF;
		t[v].i = tl;
		return;
	}
	int tm = tl + tr >> 1;
	build(t[v].l , tl , tm);
	build(t[v].r , tm + 1 , tr);
	t[v].x = min(t[t[v].l].x , t[t[v].r].x);
}
void upd(int nv , int &v , int pos , int x , int tl = 1 , int tr = n){
	if(!v) v = ++ timer;
	if(tl == tr){
		// cout << tl << ' ' << x << '\n';
		t[v].x = x;
		t[v].i = tl;
		return;
	}
	int tm = tl + tr >> 1;
	if(pos <= tm){
		t[v].r = t[nv].r;
		upd(t[nv].l , t[v].l , pos , x , tl , tm);
	}
	else{
		t[v].l = t[nv].l;
		upd(t[nv].r , t[v].r , pos , x , tm + 1 , tr);
	}
	if(t[t[v].l].x <= t[t[v].r].x){
		t[v].i = t[t[v].l].i;
	}
	else{
		t[v].i = t[t[v].r].i;
	}
	t[v].x = min(t[t[v].l].x , t[t[v].r].x);
	// cout << " v -- > " << v << ' ' << tl << ' ' << tr << ' ' << t[v].x << ' ' << t[v].i << '\n';
}
pii get(int v , int l , int r , int tl = 1 , int tr = n){
	if(tl > r || tr < l) return {INF , INF};
	if(tl >= l && tr <= r) return {t[v].x , t[v].i};
	int tm = tl + tr >> 1;
	return min(get(t[v].l , l , r , tl , tm) , get(t[v].r , l , r , tm + 1 , tr));
}
void Gold(){
	cin >> n >> k;
	set <int> st1;
	map <int,int> mp,last;
	map <int,int> mp1;
	for(int i = 1 ; i <= n ; i++){
		cin >> x[i] >> y[i];
		p[i] = {y[i] , x[i]};
	}
	sort(p + 1 , p + n + 1);
	for(int i = 1 ; i <= n ; i++){
		x[i] = p[i].S , y[i] = p[i].F;
		br[i] = {{x[i] , y[i]} , i};
	}
	sort(br + 1 , br + n + 1);
	for(int i = 1 ; i <= n ; i++){
		x[i] = br[i].F.F , y[i] = br[i].F.S , y1[i] = br[i].S;
		// cout << x[i] << ' ' << y[i] << ' ' << y1[i] << '\n';
	}
	// cout << '\n';
	int cnt = 1;
	// 1 pers
	build(root[1]);
	multiset <pair <pii , pii>> st;
	val[1][1] = 1;
	for(int i = 2 ; i <= n ; i++){
		++cnt;
		upd(root[cnt - 1] , root[cnt] , y1[i - 1] , y[i - 1] - x[i - 1]);
		// cout << "DO\n";
		val[1][i] = cnt;
		pii b = get(root[cnt] , y1[i] + 1 , n);
		st.insert({{b.F + x[i] - y[i] , b.S} , {i , 1}});
	}
	// 2 pers
	build(root[++cnt]);
	val[2][1] = cnt;
	for(int i = 2 ; i <= n ; i++){
		++cnt;
		upd(root[cnt - 1] , root[cnt] , y1[i - 1] , -x[i - 1] - y[i - 1]);
		val[2][i] = cnt;
		pii b = get(root[cnt] , 1 , y1[i] - 1);
		// cout << i << ' ' << b.F << ' ' << b.S << ' ' << x[i] + y[i] << '\n';
		st.insert({{b.F + x[i] + y[i] , b.S} , {i , 2}});
	}
	while(k--){
		pair <pii , pii> th = *st.begin();
		int i = th.S.F , d = th.F.F , yj = th.F.S , tp = th.S.S;
		cout << d << '\n';
		upd(root[val[tp][i]] , root[++cnt] , yj , INF);
		val[tp][i] = cnt;
		if(tp == 1){
			pii b = get(root[cnt] , y1[i] + 1 , n);
			st.insert({{b.F + x[i] - y[i] , b.S} , {i , 1}});
		}
		else{
			pii b = get(root[cnt] , 1 , y1[i] - 1);
			st.insert({{b.F + x[i] + y[i] , b.S} , {i , 2}});
		}
		st.erase(st.find(th));
	}
}
signed main(/*Zhunussov Temirlan*/){
	//freopen("txt.in","r",stdin);freopen("txt.out","w",stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);
	srand(time(0));
	int TT = 1;
	// cin >> TT;
	for(int i = 1 ; i <= TT ; i++){
		//cout << "Case " << i << ": ";
		Gold();
	}
}

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