Submission #37877

#	Time	Username	Problem	Language	Result	Execution time	Memory
37877		alenam0161	Mountain Trek Route (IZhO12_route)	C++14	0 / 100	13 ms	48892 KiB

route

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, k;
const int N = 1e6 + 7;
int a[N];
vector<int> v, how;
void add_point(int &aa, int &bb){
	v.push_back(aa);
	how.push_back(bb);
}

int par[N];
int sz[N];
int L[N], R[N];
int bardzr[N];

int get_par(int v){
	return (v == par[v] ? v : par[v] = get_par(par[v]));
}


vector<int> g[N];
int main() {
	scanf("%d%d", &n, &k);
	int high = 0;
	for (int i = 1; i <= n; ++i){
		scanf("%d", a + i);
		high = max(high, a[i]);
	}
	int cn = n;
	int q = 1;
	while (a[cn] == a[1]){
		cn--; q++;
	}
	if (cn == 0){
		cout << 0 << endl; return 0;
	}
	int l = 1;
	while (a[l + 1] == a[l]){
		l++; q++;
	}
	add_point(a[1], q);
	l++;
	for (; l <= cn; ++l){
		int r = l + 1;
		int cr = 1;
		while (r <= cn&&a[r] == a[l]){
			cr++; r++;
		}
		l = r - 1;
		add_point(a[r - 1], cr);
	}

	int len = v.size();
	for (int i = 0; i < len; ++i){
		par[i] = i; sz[i] = how[i]; L[i] = R[i] = i; bardzr[i] = v[i];
	//	cout << v[i] << " " << how[i] << endl;
	}
	for (int i = 0; i < len; ++i){
		int le = i - 1 + len; 
	//	cout << le << endl;
		le %= len;
		int ra = i + 1; ra %= len;
	//	cout << v[i] << " " << v[ra] << " " << v[le] << endl;
		if (v[le]>v[i] && v[i] < v[ra]){
			g[sz[i]].push_back(i);
		}
	}
	long long ans = 0;
	for (int i = 0; i <=n; ++i){
		for (int to : g[i]){
			int f = get_par(to);
		//	cout << ans << endl;
		//	cout << i << " " << to << " " << f<<" "<<k<<" "<<sz[f] << endl;
			if (to != f)break;
			int le = L[f];
			int ra = R[f];
			if (sz[f] == n)goto heracir;
			le--;
			le += len;
			le %= len;
			ra++;
			ra %= len;
			int pl = get_par(le);
			int pr = get_par(ra);
			if (sz[f] + sz[pl] == n){
				int u = bardzr[pl] - bardzr[f];
			//	cout << u << endl;
				if (u*sz[f] <= k){
					ans += u * 2;
					goto heracir;
				}
				else{
					int q = k / sz[f];
					ans += q * 2;
					goto heracir;
				}
			}
			else{
				int u = min(bardzr[pl], bardzr[pr]) - bardzr[f];
			//	cout << u << " " << pl << " " << pr << endl;
				if (u*sz[f] <= k){
					k -= u*sz[f];
					ans += u * 2;
					if (bardzr[pl] == bardzr[f]+u){
						if (bardzr[pl] == bardzr[pr]){
							par[pl] = f;
							sz[f] += sz[pl];
							L[f] = L[pl];
							par[pr] = f;
							sz[f] += sz[pr];
							R[f] = R[pr];
						}
						else{
							par[pl] = f;
							sz[f] += sz[pl];
							L[f] = L[pl];
						}
					}
					else{
						par[pr] = f;
						sz[f] += sz[pr];
						R[f] = R[pr];
					}
					bardzr[f] += u;
				}
				else{
					int q = k / sz[f];
					ans += q * 2;
					goto heracir;
				}
			}
		//	cout << "yes" << endl;
			g[sz[f]].push_back(f);
		}
	}
heracir:
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

route.cpp: In function 'int main()':
route.cpp:29:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
route.cpp:32:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
                     ^

• Subtask 1: 0 / 100