Submission #912482

#	Time	Username	Problem	Language	Result	Execution time	Memory
912482		denniskim	Road Construction (JOI21_road_construction)	C++17	100 / 100	3683 ms	859016 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, m;
pll a[1000010];
ll zipy[1000010];
priority_queue< pair<ll, pll> > pq;
ll rt1[1000010], rt2[1000010];
vector<ll> zip;
vector<ll> sad[1000010];

struct node
{
	ll L, R, gap, idx;
};

struct persistentsegtree
{
	vector<node> seg;
	
	void init(ll no, ll s, ll e)
	{
		if(s == e)
			return;
		
		seg[no].L = (ll)seg.size();
		seg.push_back({-1, -1, INF, -1});
		seg[no].R = (ll)seg.size();
		seg.push_back({-1, -1, INF, -1});
		
		init(seg[no].L, s, (s + e) >> 1);
		init(seg[no].R, ((s + e) >> 1) + 1, e);
	}
	
	void update(ll last, ll no, ll s, ll e, ll w, ll v, ll v2)
	{
		if(e < w || w < s)
			return;
		
		if(s == e)
		{
			seg[no].gap = v;
			seg[no].idx = v2;
			return;
		}
		
		ll mid = (s + e) >> 1;
		
		if(w <= mid)
		{
			seg[no].R = seg[last].R;
			
			if(seg[no].L == -1)
			{
				seg[no].L = (ll)seg.size();
				seg.push_back({-1, -1, INF, -1});
			}
			
			update(seg[last].L, seg[no].L, s, mid, w, v, v2);
		}
		
		else
		{
			seg[no].L = seg[last].L;
			
			if(seg[no].R == -1)
			{
				seg[no].R = (ll)seg.size();
				seg.push_back({-1, -1, INF, -1});
			}
			
			update(seg[last].R, seg[no].R, mid + 1, e, w, v, v2);
		}
		
		if(seg[seg[no].L].gap < seg[seg[no].R].gap)
			seg[no].gap = seg[seg[no].L].gap, seg[no].idx = seg[seg[no].L].idx;
		else
			seg[no].gap = seg[seg[no].R].gap, seg[no].idx = seg[seg[no].R].idx;
	}
	
	pll query(ll no, ll s, ll e, ll l, ll r)
	{
		if(e < l || r < s)
			return {INF, -1};
		
		if(l <= s && e <= r)
			return {seg[no].gap, seg[no].idx};
		
		pll ret;
		
		ret = {INF, -1};
		
		if(seg[no].L != -1)
			ret = min(ret, query(seg[no].L, s, (s + e) >> 1, l, r));
		
		if(seg[no].R != -1)
			ret = min(ret, query(seg[no].R, ((s + e) >> 1) + 1, e, l, r));
		
		return ret;
	}
}segt1, segt2;

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	for(ll i = 1 ; i <= n ; i++)
		cin >> a[i].fi >> a[i].se;
	
	sort(a + 1, a + 1 + n);
	
	for(ll i = 1 ; i <= n ; i++)
		zip.push_back(a[i].se);
	
	compress(zip);
	
	ll siz = (ll)zip.size();
	
	for(ll i = 1 ; i <= n ; i++)
	{
		zipy[i] = lower_bound(zip.begin(), zip.end(), a[i].se) - zip.begin() + 1;
		sad[zipy[i]].push_back(i);
	}
	
	rt1[n] = (ll)segt1.seg.size();
	segt1.seg.push_back({-1, -1, INF, -1});
	segt1.init(rt1[n], 1, siz);
	
	rt2[n] = (ll)segt2.seg.size();
	segt2.seg.push_back({-1, -1, INF, -1});
	segt2.init(rt2[n], 1, siz);
	
	for(ll i = n - 1 ; i >= 1 ; i--)
	{
		rt1[i] = (ll)segt1.seg.size();
		segt1.seg.push_back({-1, -1, INF, -1});
		segt1.update(rt1[i + 1], rt1[i], 1, siz, zipy[i + 1], a[i + 1].fi + a[i + 1].se, i + 1);
		
		rt2[i] = (ll)segt2.seg.size();
		segt2.seg.push_back({-1, -1, INF, -1});
		segt2.update(rt2[i + 1], rt2[i], 1, siz, zipy[i + 1], a[i + 1].fi - a[i + 1].se, i + 1);
	}
	
	for(ll i = 1 ; i < n ; i++)
	{
		pll gap1 = segt1.query(rt1[i], 1, siz, zipy[i], siz);
		pll gap2 = segt2.query(rt2[i], 1, siz, 1, zipy[i]);
		
		gap1.fi -= (a[i].fi + a[i].se);
		gap2.fi -= (a[i].fi - a[i].se);
		gap1 = min(gap1, gap2);
		
		pq.push({-gap1.fi, {i, gap1.se}});
	}
	
	while(!pq.empty() && m)
	{
		pair<ll, pll> qq = pq.top();
		pq.pop();
		
		cout << -qq.fi en;
		m--;
		
		ll i = qq.se.fi;
		ll won = rt1[i], won2 = rt2[i];
		ll Y = zipy[qq.se.se];
		ll idx2 = upper_bound(sad[Y].begin(), sad[Y].end(), qq.se.se) - sad[Y].begin();
		ll V1 = 0, V2 = 0;
		
		if(idx2 >= (ll)sad[Y].size())
			V1 = INF, V2 = -1;
		
		else
		{
			ll w = sad[Y][idx2];
			V1 = a[w].fi + a[w].se, V2 = w;
		}
		
		rt1[i] = (ll)segt1.seg.size();
		segt1.seg.push_back({-1, -1, INF, -1});
		segt1.update(won, rt1[i], 1, siz, zipy[qq.se.se], V1, V2);
		
		if(idx2 >= (ll)sad[Y].size())
			V1 = INF, V2 = -1;
		
		else
		{
			ll w = sad[Y][idx2];
			V1 = a[w].fi - a[w].se, V2 = w;
		}
		
		rt2[i] = (ll)segt2.seg.size();
		segt2.seg.push_back({-1, -1, INF, -1});
		segt2.update(won2, rt2[i], 1, siz, zipy[qq.se.se], V1, V2);
		
		pll gap1 = segt1.query(rt1[i], 1, siz, zipy[i], siz);
		pll gap2 = segt2.query(rt2[i], 1, siz, 1, zipy[i]);
		
		gap1.fi -= (a[i].fi + a[i].se);
		gap2.fi -= (a[i].fi - a[i].se);
		
		gap1 = min(gap1, gap2);
		pq.push({-gap1.fi, {i, gap1.se}});
	}
	
	return 0;
}

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