Submission #625958

#TimeUsernameProblemLanguageResultExecution timeMemory
625958ITORadio Towers (IOI22_towers)C++17
0 / 100
4094 ms13500 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; int n, h[100000], hi[100000]; vector<pair<int, int>> pv, ppv; int av[400000]; vector<int> aa[400000]; int build(int id, int ll, int rr) { if (ll == rr) { av[id] = h[ll]; //aa[id].push_back(h[ll]); } else { int m = (ll + rr) / 2, i = 0, j = 0; av[id] = max(build(id * 2, ll, m), build(id * 2 + 1, m + 1, rr)); /*while (i < aa[id * 2].size() && j < aa[id * 2 + 1].size()) { if (aa[id * 2][i] <= aa[id * 2 + 1][j]) { aa[id].push_back(aa[id * 2][i]); i++; } else { aa[id].push_back(aa[id * 2 + 1][j]); j++; } } while (i < aa[id * 2].size()) { aa[id].push_back(aa[id * 2][i]); i++; } while (j < aa[id * 2 + 1].size()) { aa[id].push_back(aa[id * 2 + 1][j]); j++; }*/ } return av[id]; } int ma(int id, int l, int r, int ll, int rr) { if (r < ll || l > rr) return 0; if (ll >= l && rr <= r) return av[id]; int m = (l + r) / 2; return max(ma(id * 2, l, r, ll, m), ma(id * 2 + 1, l, r, m + 1, rr)); } int lar(int id, int va, int l, int r, int ll, int rr) { if (r < ll || l > rr || av[id] < va) return -1; if (ll == rr) return ll; int m = (l + r) / 2; int te = lar(id * 2 + 1, va, l, r, m + 1, rr); if (te >= 0) return te; return lar(id * 2, va, l, r, ll, m); } int lal(int id, int va, int l, int r, int ll, int rr) { if (r < ll || l > rr || av[id] < va) return -1; if (ll == rr) return ll; int m = (l + r) / 2; int te = lar(id * 2, va, l, r, ll, m); if (te >= 0) return te; return lar(id * 2 + 1, va, l, r, m + 1, rr); } int bel(int id, int va, int l, int r, int ll, int rr) { if (r < ll || l > rr) return 0; if (ll == rr) { return upper_bound(aa[id].begin(), aa[id].end(), va) - aa[id].begin(); } int m = (l + r) / 2; return bel(id * 2, va, l, r, ll, m) + bel(id * 2 + 1, va, l, r, m + 1, rr); } void init(int N, std::vector<int> H) { n = N; pv.push_back({1000000001, -1}); for (int i = 0; i < N; i++) { h[i] = H[i]; int te = pv.size(); if (te >= 2 && ((pv[te - 1].first > pv[te - 2].first && h[i] > pv[te - 1].first) || (pv[te - 1].first < pv[te - 2].first && h[i] < pv[te - 1].first))) { pv[te - 1] = make_pair(h[i], i); } else { pv.push_back({h[i], i}); } hi[i] = (pv.size() - 1); } for (int i = 1; i < pv.size(); i += 2) { if (i == pv.size() - 1) ppv.push_back({pv[i - 1].first - pv[i].first, pv[i].second}); else ppv.push_back({min(pv[i - 1].first - pv[i].first, pv[i + 1].first - pv[i].first), pv[i].second}); } build(1, 0, N - 1); } int max_towers(int L, int R, int D) { int c = 1, co = 1, bo = 1, ex = 2000000000; for (int i = L; i <= R; i++) { if (bo == 1) { if (h[i] > ex) ex = h[i]; else if (h[i] <= ex - D) { bo = 0; ex = h[i]; co++; } } else { if (h[i] < ex) ex = h[i]; else if (h[i] >= ex - D) { bo = 1; ex = h[i]; } } } return co; }

Compilation message (stderr)

towers.cpp: In function 'int build(int, int, int)':
towers.cpp:16:28: warning: unused variable 'i' [-Wunused-variable]
   16 |     int m = (ll + rr) / 2, i = 0, j = 0;
      |                            ^
towers.cpp:16:35: warning: unused variable 'j' [-Wunused-variable]
   16 |     int m = (ll + rr) / 2, i = 0, j = 0;
      |                                   ^
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for (int i = 1; i < pv.size(); i += 2) {
      |                   ~~^~~~~~~~~~~
towers.cpp:82:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     if (i == pv.size() - 1) ppv.push_back({pv[i - 1].first - pv[i].first, pv[i].second});
      |         ~~^~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:89:7: warning: unused variable 'c' [-Wunused-variable]
   89 |   int c = 1, co = 1, bo = 1, ex = 2000000000;
      |       ^
#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...