Submission #817078

#TimeUsernameProblemLanguageResultExecution timeMemory
817078finn__Radio Towers (IOI22_towers)C++17
4 / 100
4019 ms17488 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; template <typename T, size_t L> struct segtree_max { T t[L << 1]; void update(size_t i, T x) { i += L; t[i] = max(t[i], x); while (i >>= 1) t[i] = max(t[i << 1], t[i << 1 | 1]); } T range_max(size_t i, size_t j) { i += L, j += L; T x = numeric_limits<T>::min(); while (i <= j) { if (i & 1) x = max(x, t[i++]); if (!(j & 1)) x = max(x, t[j--]); i >>= 1; j >>= 1; } return x; } void reset() { memset(t, 0, sizeof t); } }; template <typename T, size_t L> struct fenwick_tree { T t[L]; void update(int64_t i, T x) { ++i; while (i <= L) t[i - 1] += x, i += i & -i; } T range_sum(int64_t i, int64_t j) { ++j; T x = 0; while (j) x += t[j - 1], j -= j & -j; while (i) x -= t[i - 1], i -= i & -i; return x; } }; constexpr size_t N = 100000; bool subtask1; int h[N], coords[3 * N]; size_t n, peak_pos; segtree_max<int64_t, 1 << 19> towers, intermediate; fenwick_tree<int, N> valleys; void init(int n_, vector<int> h_) { n = n_; copy(h_.begin(), h_.end(), h); bool increasing = 1; subtask1 = 1; for (size_t i = 0; i + 1 < n; ++i) { if (h[i] < h[i + 1] && !increasing) { subtask1 = 0; break; } if (h[i] > h[i + 1]) increasing = 0; } if (subtask1) { while (peak_pos + 1 < n && h[peak_pos + 1] > h[peak_pos]) ++peak_pos; return; } for (size_t i = 0; i < n; ++i) if ((!i || h[i - 1] > h[i]) && (i + 1 == n || h[i + 1] > h[i])) valleys.update(i, 1); } size_t ind(int64_t coord) { return lower_bound(coords, coords + 3 * n, coord) - coords; } int max_towers(int l, int r, int d) { if (subtask1) { if (l >= peak_pos || r <= peak_pos) return 1; return (h[peak_pos] >= h[l] + d && h[peak_pos] >= h[r] + d) + 1; } else if (d == 1) { return valleys.range_sum(l, r); } else { memcpy(coords, h, sizeof h); for (size_t i = 0; i < n; ++i) coords[n + i] = coords[i] + d, coords[2 * n + i] = coords[i] - d; sort(coords, coords + 3 * n); towers.reset(); intermediate.reset(); towers.update(ind(h[l]), 1); int ans = 1; for (size_t i = l + 1; i <= r; ++i) { // as intermediate int64_t v = towers.range_max(0, ind(h[i] - d)); intermediate.update(ind(h[i]), v); // as tower v = intermediate.range_max(ind(h[i] + d), 3 * n - 1) + 1; towers.update(ind(h[i]), v); ans = max<int>(ans, v); } return ans; } }

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:107:15: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         if (l >= peak_pos || r <= peak_pos)
      |             ~~^~~~~~~~~~~
towers.cpp:107:32: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         if (l >= peak_pos || r <= peak_pos)
      |                              ~~^~~~~~~~~~~
towers.cpp:127:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |         for (size_t i = l + 1; i <= r; ++i)
      |                                ~~^~~~
towers.cpp: In instantiation of 'void fenwick_tree<T, L>::update(int64_t, T) [with T = int; long unsigned int L = 100000; int64_t = long int]':
towers.cpp:98:32:   required from here
towers.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   47 |         while (i <= L)
      |                ~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...