Submission #95842

#TimeUsernameProblemLanguageResultExecution timeMemory
95842diamond_dukeSparklers (JOI17_sparklers)C++11
100 / 100
400 ms16892 KiB
#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);
   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...