Submission #95842

#	Time	Username	Problem	Language	Result	Execution time	Memory
95842		diamond_duke	Sparklers (JOI17_sparklers)	C++11	100 / 100	400 ms	16892 KiB

sparklers

#include <functional>
#include <cstdio>
using ll = long long;
struct ST_table
{
	std::function<int (int, int)> comp;
	int emp, lg[100005], arr[25][100005];
	template <typename T> ST_table(int n, int _emp, T _comp) : comp(_comp), emp(_emp)
	{
		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)
	{
		if (l > r)
			return emp;
		int len = lg[r - l + 1];
		return comp(arr[len][l], arr[len][r - (1 << len) + 1]);
	}
};
ll val[100005];
int arr[100005], st[100005], pre[100005], nxt[100005];
inline bool check(int n, int stp, ll lim)
{
	for (int i = 0; i < n; i++)
		val[i] = arr[i] - lim * i;
	val[n] = 1e18;
	val[n + 1] = -1e18;
	ST_table qmin(n, n, [&] (int x, int y) { return val[x] < val[y] ? x : y; });
	ST_table qmax(n, n + 1, [&] (int x, int y) { return val[x] > val[y] ? x : y; });
	int tp = 0;
	st[tp] = -1;
	for (int i = 0; i < n; i++)
	{
		while (tp && val[st[tp]] <= val[i])
			tp--;
		pre[i] = st[tp];
		st[++tp] = i;
	}
	tp = 0;
	st[tp] = n;
	for (int i = n - 1; i >= 0; i--)
	{
		while (tp && val[st[tp]] >= val[i])
			tp--;
		nxt[i] = st[tp];
		st[++tp] = i;
	}
	int l = stp, r = stp;
	while (l || r != n - 1)
	{
		int x = pre[l], y = nxt[r];
		if (~x && val[qmin(x + 1, l - 1)] >= val[r])
			l = x;
		else if (y != n && val[qmax(r + 1, y - 1)] <= val[l])
			r = y;
		else
		{
			if (!l)
				return val[qmax(r + 1, n - 1)] <= val[l];
			if (r == n - 1)
				return val[qmin(0, l - 1)] >= val[r];
			x = qmin(0, l - 1);
			y = qmax(r + 1, n - 1);
			if (val[x] < val[r] || val[y] > val[l])
				return false;
			int a = qmax(0, x), b = qmin(y, n - 1);
			if (val[a] >= val[y])
				l = a;
			else if (val[b] <= val[x])
				r = b;
			else
				return false;
		}
	}
	return true;
}
int main()
{
	// freopen("loj-2392.in", "r", stdin);
	int n, stp, T;
	scanf("%d%d%d", &n, &stp, &T);
	for (int i = 0; i < n; i++)
		scanf("%d", arr + i);
	int l = 0, r = (arr[n - 1] - arr[0]) / T / 2 + 1, res = -1;
	while (l <= r)
	{
		int m = l + r >> 1;
		if (check(n, stp - 1, (ll)2 * m * T))
		{
			res = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}
	printf("%d\n", res);
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:96:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
sparklers.cpp: In instantiation of 'ST_table::ST_table(int, int, T) [with T = check(int, int, ll)::<lambda(int, int)>]':
sparklers.cpp:37:76:   required from here
sparklers.cpp:18: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 instantiation of 'ST_table::ST_table(int, int, T) [with T = check(int, int, ll)::<lambda(int, int)>]':
sparklers.cpp:38:80:   required from here
sparklers.cpp:18:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
sparklers.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &stp, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", arr + i);
   ~~~~~^~~~~~~~~~~~~~~

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