Submission #37817

#	Time	Username	Problem	Language	Result	Execution time	Memory
37817		14kg	Mountain Trek Route (IZhO12_route)	C++11	0 / 100	2000 ms	23792 KiB

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)

using namespace std;
typedef pair<int, pair<int, int> > pip;
int n, m, in[N], Q_sum;
bool cc[N];
pair<int, int> go1[N], go2[N];
//priority_queue<pip, vector<pip>, greater<pip> > Q;
set<pip> S;

void S_push(pip x) {
	set<pip>::iterator it;
	S.insert(x), Q_sum += x.first;
/*	while (S.begin() != S.end() && Q_sum > m) {
		it = S.end(), it--, Q_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;

	//freopen("input.txt", "r", stdin);

	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()) {
		// printf("!");
		temp = *S.begin(), S.erase(S.begin());
		if (m < temp.first) break;
		len = temp.first, x = temp.second.first, y = temp.second.second;
		m -= len, tot++;

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

		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);
	// getchar(), getchar();
}

Compilation message (stderr)

route.cpp: In function 'int main()':
route.cpp:35: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:37:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &in[i]);
                      ^
route.cpp:29:12: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int path, x, y, len, tot = 0, tx, ty;
            ^
route.cpp:50:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (in[path] < in[s] && check) {
                     ^

• Subtask 1: 0 / 100