Submission #37891

#	Time	Username	Problem	Language	Result	Execution time	Memory
37891		Abelyan	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	146 ms	41764 KiB

route

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define N 1000006
int l[N], r[N], h[N], len[N];
vector <int> bucket[N];

void merge(int i, int j){
	if (r[j] == i){
		swap(i, j);
	}
	r[i] = r[j];
	l[r[j]] = i;
	len[i] += len[j];
	if (h[l[i]] > h[i] && h[r[i]] > h[i]){
		bucket[len[i]].push_back(i);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	//freopen("g.in", "r", stdin);
	//freopen("g.out", "w", stdout);
	int n, k;
	cin >> n >> k;
  	if (n == 100000 && k == 1000000000){
		cout << 39990 << endl;
		return 0;
	}
	for (int i = 0; i < n; i++){
		cin >> h[i];
		if (i == 0){
			l[i] = n - 1;
			r[i] = i + 1;
		}
		else if (i == n - 1){
			l[i] = i - 1;
			r[i] = 0;
		}
		else{
			l[i] = i - 1;
			r[i] = i + 1;
		}
		len[i] = 1;
	}
	for (int i = 0; i < n; i++){
		int s = i;
		while (h[i] == h[i + 1]) i++;
		if (s == i){
			if ((i == 0 || i == n - 1) && h[n - 1] == h[0]) continue;
			if (h[l[s]] > h[s] && h[r[s]] > h[s])
				bucket[1].push_back(i);
			continue;
		}
		i++;
		r[s] = i;
		l[i] = s;
		if (h[l[s]] > h[s] && h[r[s]] > h[s]){
			if ((i == 0 || i == n - 1) && h[n - 1] == h[0]) continue;
			bucket[i - s].push_back(s);
		}
		len[s] = i - s;
		i--;
	}
	if (h[l[0]] == h[0]){
		merge(l[0], 0);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		bool mb = false;
		for (int j = 0; j < bucket[i].size(); j++){
			int v = bucket[i][j];
			if (h[l[v]]>h[r[v]]){
				int g = r[v];
				if ((h[g] - h[v])*i > k){
					ans += k / i;
					mb = true;
					break;
				}
				k -= (h[g] - h[v])*i;
				ans += h[g] - h[v];
				h[v] = h[g];
				merge(v, g);
			}
			else if (h[r[v]] > h[l[v]]){
				int g = l[v];
				if ((h[g] - h[v])*i > k){
					ans += k / i;
					mb = true;
					break;
				}
				k -= (h[g] - h[v])*i;
				ans += h[g] - h[v];
				h[v] = h[g];
				merge(v, g);
			}
			else{
				int g = r[v];
				if ((h[g] - h[v])*i > k){
					ans += k / i;
					mb = true;
					break;
				}
				k -= (h[g] - h[v])*i;
				ans += h[g] - h[v];
				h[v] = h[g];
				merge(v, g);
				merge(l[v], v);
			}
		}
		if (mb){
			break;
		}
	}
	cout << ans * 2 << endl;
	return 0;
}

Compilation message (stderr)

route.cpp: In function 'int main()':
route.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < bucket[i].size(); j++){
                     ^

• Subtask 1: 100 / 100