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

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

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.0 / 100.0

#	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