Submission #625960

#	Time	Username	Problem	Language	Result	Execution time	Memory
625960		ITO	Radio Towers (IOI22_towers)	C++17	27 / 100	4053 ms	13916 KiB

towers

#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 = 0, 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] - D >= ex) {
        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 = 0, bo = 1, ex = 2000000000;
      |       ^

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23