Submission #37849

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
37849	2017-12-28T10:26:21 Z	14kg	Mountain Trek Route (IZhO12_route)	C++11	100 / 100	229 ms	23792 KB

route

#include <stdio.h>
#include <set>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define N 1000001
#define next(x) (x==n?1:x+1)
#define before(x) (x==1?n:x-1)
#define min2(x,y) (x<y?x:y)

using namespace std;
typedef pair<int, pair<int, int> > pip;
int n, m, in[N], S_sum;
bool cc[N];
pair<int, int> go1[N], go2[N];
set<pip> S;

void S_push(pip x) {
	set<pip>::iterator it;
	S.insert(x), S_sum += x.first;
	while (S.begin() != S.end() && S_sum > m) {
		it = S.end(), it--, S_sum -= it->first;
		S.erase(it);
	}
}

int main() {
	int s, num = -1;
	int path, x, y, len, tot = 0, tx, ty;
	bool check;
	pip temp;

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &in[i]);
		if (num < in[i]) num = in[i], s = i;
	}

	path = s, len = 0, check = false;;
	for (int i = next(s); i != s; i = next(i)) {
		if (in[path] > in[i]) x = i, len = 1, check = true;
		if (in[path] == in[i]) len++;
		if (in[path] < in[i] && check) {
			S_push({ len,{ x, path } }), check = false;
			go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
		} path = i;
	}
	if (in[path] < in[s] && check) {
		S_push({ len,{ x, path } });
		go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
	}

	while (S.end() != S.begin()) {
		temp = *S.begin(), S.erase(S.begin());
		if (m < temp.first) break;
		len = temp.first, x = temp.second.first, y = temp.second.second;
		
		num = min2(min2(in[before(x)] - in[x], in[next(y)] - in[y]), m / len);
		tot += num, m -= len*num, S_sum -= len*num;

		in[x]+=num;
		if (x != y) in[y] += num;

		tx = x, num = 0, path = len;
		while (in[before(tx)] == in[tx]) {
			num++, len++, tx = before(tx);
			if (go1[tx].second) len += go1[tx].second, tx = go1[tx].first;
			if (num > n) break;
		}
		go1[x] = { tx,len - path };
		if (in[before(tx)] == in[tx]) break;
		if (in[before(tx)] < in[tx]) continue;

		ty = y, path = len;
		while (in[ty] == in[next(ty)]) {
			len++, ty = next(ty);
			if (go2[ty].second) len += go2[ty].second, ty = go2[ty].first;
		}
		go2[y] = { ty,len - path };

		if (in[ty] < in[next(ty)]) {
			S_push({ len,{ tx,ty } });
			go1[ty] = { tx,len - 1 }, go2[tx] = { ty,len - 1 };
		}
	} printf("%d", tot * 2);
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:34:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
route.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &in[i]);
                      ^
route.cpp:49:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (in[path] < in[s] && check) {
                     ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	21680 KB	Output is correct
2	Correct	0 ms	21680 KB	Output is correct
3	Correct	0 ms	21680 KB	Output is correct
4	Correct	0 ms	21680 KB	Output is correct
5	Correct	0 ms	21680 KB	Output is correct
6	Correct	0 ms	21680 KB	Output is correct
7	Correct	0 ms	21680 KB	Output is correct
8	Correct	0 ms	21680 KB	Output is correct
9	Correct	0 ms	21680 KB	Output is correct
10	Correct	19 ms	21680 KB	Output is correct
11	Correct	23 ms	23792 KB	Output is correct
12	Correct	13 ms	21680 KB	Output is correct
13	Correct	169 ms	21680 KB	Output is correct
14	Correct	229 ms	21680 KB	Output is correct
15	Correct	169 ms	21680 KB	Output is correct
16	Correct	146 ms	21680 KB	Output is correct
17	Correct	186 ms	21680 KB	Output is correct
18	Correct	183 ms	21680 KB	Output is correct
19	Correct	203 ms	21680 KB	Output is correct
20	Correct	126 ms	21680 KB	Output is correct