oj.uz

Submission #526338

# Submission time Handle Problem Language Result Execution time Memory
526338 2022-02-14T11:27:09 Z keta_tsimakuridze Mountain Trek Route (IZhO12_route) C++14
100 / 100
 373 ms 49000 KB 
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, n, k, p[N], a[N], b[N], l[N], r[N];
int find(int u) {
	return (p[u] == u ? u : p[u] = find(p[u]));
}
void merge(int u, int v) {
	u = find(u); v = find(v);
	if(u == v) return;
	p[v] = u;
	l[u] = min(l[u], l[v]);
	r[u] = max(r[u], r[v]);
}
main(){
	cin >> n >> k;
	pii mx; mx = {0, 0};
	for(int i = 1; i <= n; i++) cin >> b[i], p[i] = i, l[i] = r[i] = i, mx = max(mx, {b[i], i});
	int c = 0;
	for(int i = mx.s; i <= n; i++) a[++c] = b[i];
	for(int i = 1; i < mx.s + 1; i++) a[++c] = b[i];
	set<pii> s;
	for(int i = 1; i <= n; i++) {
		int j = i - 1; 
		while(j < n && a[j + 1] == a[i]) j++, merge(i, j);
		find(i);
		if(a[l[p[i]] - 1] > a[i] && a[r[p[i]] + 1] > a[i]) s.insert({r[p[i]] - l[p[i]] + 1, i}); 
		
		i = j;
	} 
	int ans = 0;
	while(k && s.size()) {
		pii x = *s.begin();
		s.erase(x);
		int i = x.s, len = x.f; find(i);
		i = p[i];
		int need = min(a[l[p[i]] - 1], a[r[p[i]] + 1]) - a[p[i]]; 
		if(need * len >= k) {
			
			ans += k / len * 2; 
			k = 0;
			break;
		}
		ans += need * 2;
		k -= need * len;
		a[p[i]] = min(a[l[p[i]] - 1], a[r[p[i]] + 1]);
		if(a[p[i]] == a[l[p[i]] - 1]) {
			merge(p[i], l[p[i]] - 1);
		}
		if(a[p[i]] == a[r[p[i]] + 1]) {
			merge(p[i], r[p[i]] + 1);
		}
		if(a[l[p[i]] - 1] > a[p[i]] && a[r[p[i]] + 1] > a[p[i]]) s.insert({r[p[i]] - l[p[i]] + 1, i}); 
	}
	cout << ans;
}

Compilation message

route.cpp:19:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main(){
      | ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 37 ms 4212 KB Output is correct
11 Correct 44 ms 6200 KB Output is correct
12 Correct 35 ms 4148 KB Output is correct
13 Correct 358 ms 47024 KB Output is correct
14 Correct 371 ms 48980 KB Output is correct
15 Correct 318 ms 47004 KB Output is correct
16 Correct 342 ms 47896 KB Output is correct
17 Correct 344 ms 48008 KB Output is correct
18 Correct 362 ms 48800 KB Output is correct
19 Correct 373 ms 49000 KB Output is correct
20 Correct 263 ms 45252 KB Output is correct