Submission #96988

#	Time	Username	Problem	Language	Result	Execution time	Memory
96988		diamond_duke	Sparklers (JOI17_sparklers)	C++11	100 / 100	366 ms	17016 KiB

sparklers

#include <algorithm>
#include <cstdio>
using ll = long long;
struct ST_table
{
	using func_T = int (*)(int, int);
	int n, lg[100005], arr[25][100005];
	func_T comp;
	ST_table(int _n, func_T _comp) : n(_n), comp(_comp)
	{
		lg[0] = lg[1] = 0;
		for (int i = 2; i <= n; i++)
			lg[i] = lg[i >> 1] + 1;
		for (int i = 0; i < n; i++)
			arr[0][i] = i;
		for (int i = 1; i <= lg[n]; i++)
		{
			for (int j = 0; j + (1 << i) <= n; j++)
				arr[i][j] = comp(arr[i - 1][j], arr[i - 1][j + (1 << i - 1)]);
		}
	}
	inline int operator ()(int l, int r)
	{
		int len = lg[r - l + 1];
		return comp(arr[len][l], arr[len][r - (1 << len) + 1]);
	}
};
int pos[100005], stk[100005], pre[100005], nxt[100005];
ll arr[100005];
inline int smaller(int x, int y) { return arr[x] < arr[y] ? x : y; }
inline int larger(int x, int y) { return arr[x] > arr[y] ? x : y; }
inline bool check(int n, int st, ll T)
{
	for (int i = 0; i < n; i++)
		arr[i] = pos[i] - T * i;
	ST_table query_min(n, smaller), query_max(n, larger);
	auto find_bigger = [&] (int *res)
	{
		int tp = 0;
		stk[tp] = -1;
		for (int i = 0; i < n; i++)
		{
			while (tp && arr[stk[tp]] <= arr[i])
				tp--;
			res[i] = stk[tp];
			stk[++tp] = i;
		}
		std::reverse(arr, arr + n);
		for (int i = 0; i < n; i++)
			arr[i] *= -1;
	};
	find_bigger(pre);
	find_bigger(nxt);
	std::reverse(nxt, nxt + n);
	for (int i = 0; i < n; i++)
		nxt[i] = n - nxt[i] - 1;
	int l = st, r = st;
	while (l || r != n - 1)
	{
		auto try_l = [&] (int x)
		{
			if (x < 0 || arr[query_min(x, l - 1)] < arr[r])
				return false;
			l = x;
			return true;
		};
		auto try_r = [&] (int y)
		{
			if (y >= n || arr[query_max(r + 1, y)] > arr[l])
				return false;
			r = y;
			return true;
		};
		if (try_l(pre[l]) || try_r(nxt[r]))
			continue;
		if (!l)
			return arr[query_max(r + 1, n - 1)] <= arr[l];
		if (r == n - 1)
			return arr[query_min(0, l - 1)] >= arr[r];
		int x = query_min(0, l - 1), y = query_max(r + 1, n - 1);
		if (arr[x] < arr[r] || arr[y] > arr[l])
			return false;
		int a = query_max(0, x), b = query_min(y, n - 1);
		if (arr[a] >= arr[y])
			l = a;
		else if (arr[b] <= arr[x])
			r = b;
		else
			return false;
	}
	return true;
}
int main()
{
	// freopen("JOISC2017-D1T3.in", "r", stdin);
	int n, st, T;
	scanf("%d%d%d", &n, &st, &T);
	for (int i = 0; i < n; i++)
		scanf("%d", pos + i);
	int l = 0, r = 1e9, res = -1;
	while (l <= r)
	{
		int m = l + r >> 1;
		if (check(n, st - 1, (ll)m * T * 2))
		{
			res = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}
	printf("%d\n", res);
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In constructor 'ST_table::ST_table(int, ST_table::func_T)':
sparklers.cpp:19:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     arr[i][j] = comp(arr[i - 1][j], arr[i - 1][j + (1 << i - 1)]);
                                                          ~~^~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:103:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
sparklers.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &st, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", pos + i);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50