oj.uz

Submission #912482

# Submission time Handle Problem Language Result Execution time Memory
912482 2024-01-19T14:25:56 Z denniskim Road Construction (JOI21_road_construction) C++17
100 / 100
 3683 ms 859016 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 231828 KB Output is correct
2 Correct 573 ms 232056 KB Output is correct
3 Correct 473 ms 232884 KB Output is correct
4 Correct 334 ms 233000 KB Output is correct
5 Correct 480 ms 231152 KB Output is correct
6 Correct 11 ms 32976 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 93348 KB Output is correct
2 Correct 241 ms 93276 KB Output is correct
3 Correct 74 ms 49764 KB Output is correct
4 Correct 160 ms 92748 KB Output is correct
5 Correct 149 ms 92888 KB Output is correct
6 Correct 149 ms 93216 KB Output is correct
7 Correct 160 ms 94240 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1725 ms 454136 KB Output is correct
2 Correct 1641 ms 453992 KB Output is correct
3 Correct 8 ms 31320 KB Output is correct
4 Correct 90 ms 76196 KB Output is correct
5 Correct 465 ms 252516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1725 ms 454136 KB Output is correct
2 Correct 1641 ms 453992 KB Output is correct
3 Correct 8 ms 31320 KB Output is correct
4 Correct 90 ms 76196 KB Output is correct
5 Correct 465 ms 252516 KB Output is correct
6 Correct 1609 ms 451092 KB Output is correct
7 Correct 1617 ms 452672 KB Output is correct
8 Correct 9 ms 31336 KB Output is correct
9 Correct 8 ms 31408 KB Output is correct
10 Correct 1596 ms 450692 KB Output is correct
11 Correct 87 ms 76100 KB Output is correct
12 Correct 469 ms 252904 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 231828 KB Output is correct
2 Correct 573 ms 232056 KB Output is correct
3 Correct 473 ms 232884 KB Output is correct
4 Correct 334 ms 233000 KB Output is correct
5 Correct 480 ms 231152 KB Output is correct
6 Correct 11 ms 32976 KB Output is correct
7 Correct 2208 ms 452436 KB Output is correct
8 Correct 2241 ms 451824 KB Output is correct
9 Correct 350 ms 232932 KB Output is correct
10 Correct 1156 ms 442312 KB Output is correct
11 Correct 1557 ms 444864 KB Output is correct
12 Correct 431 ms 278116 KB Output is correct
13 Correct 468 ms 260740 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 231828 KB Output is correct
2 Correct 573 ms 232056 KB Output is correct
3 Correct 473 ms 232884 KB Output is correct
4 Correct 334 ms 233000 KB Output is correct
5 Correct 480 ms 231152 KB Output is correct
6 Correct 11 ms 32976 KB Output is correct
7 Correct 265 ms 93348 KB Output is correct
8 Correct 241 ms 93276 KB Output is correct
9 Correct 74 ms 49764 KB Output is correct
10 Correct 160 ms 92748 KB Output is correct
11 Correct 149 ms 92888 KB Output is correct
12 Correct 149 ms 93216 KB Output is correct
13 Correct 160 ms 94240 KB Output is correct
14 Correct 1725 ms 454136 KB Output is correct
15 Correct 1641 ms 453992 KB Output is correct
16 Correct 8 ms 31320 KB Output is correct
17 Correct 90 ms 76196 KB Output is correct
18 Correct 465 ms 252516 KB Output is correct
19 Correct 1609 ms 451092 KB Output is correct
20 Correct 1617 ms 452672 KB Output is correct
21 Correct 9 ms 31336 KB Output is correct
22 Correct 8 ms 31408 KB Output is correct
23 Correct 1596 ms 450692 KB Output is correct
24 Correct 87 ms 76100 KB Output is correct
25 Correct 469 ms 252904 KB Output is correct
26 Correct 2208 ms 452436 KB Output is correct
27 Correct 2241 ms 451824 KB Output is correct
28 Correct 350 ms 232932 KB Output is correct
29 Correct 1156 ms 442312 KB Output is correct
30 Correct 1557 ms 444864 KB Output is correct
31 Correct 431 ms 278116 KB Output is correct
32 Correct 468 ms 260740 KB Output is correct
33 Correct 3683 ms 858392 KB Output is correct
34 Correct 3564 ms 859016 KB Output is correct
35 Correct 2174 ms 857368 KB Output is correct
36 Correct 742 ms 458560 KB Output is correct
37 Correct 706 ms 460064 KB Output is correct
38 Correct 748 ms 460592 KB Output is correct