Submission #526337

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526337	2022-02-14T11:26:45 Z	keta_tsimakuridze	Mountain Trek Route (IZhO12_route)	C++14	0 / 100	94 ms	9908 KB

route

#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 = 2e5 + 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 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	300 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	308 KB	Output is correct
10	Correct	34 ms	4972 KB	Output is correct
11	Correct	45 ms	7176 KB	Output is correct
12	Correct	35 ms	5172 KB	Output is correct
13	Incorrect	94 ms	9908 KB	Output isn't correct
14	Halted	0 ms	0 KB	-