Submission #37891

# Submission time Handle Problem Language Result Execution time Memory
37891 2017-12-28T19:33:20 Z Abelyan Mountain Trek Route (IZhO12_route) C++14
100 / 100
146 ms 41764 KB
#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

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++){
                     ^
# Verdict Execution time Memory Grader output
1 Correct 6 ms 41236 KB Output is correct
2 Correct 6 ms 41236 KB Output is correct
3 Correct 3 ms 41236 KB Output is correct
4 Correct 9 ms 41236 KB Output is correct
5 Correct 3 ms 41236 KB Output is correct
6 Correct 9 ms 41236 KB Output is correct
7 Correct 3 ms 41236 KB Output is correct
8 Correct 3 ms 41236 KB Output is correct
9 Correct 6 ms 41236 KB Output is correct
10 Correct 23 ms 41236 KB Output is correct
11 Correct 16 ms 41656 KB Output is correct
12 Correct 3 ms 41236 KB Output is correct
13 Correct 146 ms 41236 KB Output is correct
14 Correct 126 ms 41236 KB Output is correct
15 Correct 139 ms 41764 KB Output is correct
16 Correct 113 ms 41368 KB Output is correct
17 Correct 143 ms 41368 KB Output is correct
18 Correct 129 ms 41236 KB Output is correct
19 Correct 143 ms 41236 KB Output is correct
20 Correct 119 ms 41236 KB Output is correct