Submission #626505

#	Time	Username	Problem	Language	Result	Execution time	Memory
626505		ITO	Radio Towers (IOI22_towers)	C++17	37 / 100	1195 ms	29936 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
int n, h[100005], hi[100005], mama[100005];
vector<pair<int, int>> pv;

int av[400000], bv[400000];
vector<int> aa[400000];

int build(int id, int ll, int rr) {
  if (ll == rr) {
    av[id] = h[ll];
    bv[id] = mama[ll];
    if (bv[id] == 2000000001) bv[id] = -1000000001;
    aa[id].push_back(mama[ll]);
  } else {
    int m = (ll + rr) / 2, i = 0, j = 0;
    av[id] = min(build(id * 2, ll, m), build(id * 2 + 1, m + 1, rr));
    bv[id] = max(bv[id * 2], bv[id * 2 + 1]);
    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 mi(int id, int l, int r, int ll, int rr) {
  if (r < ll || l > rr) return 2000000001;
  if (ll >= l && rr <= r) return av[id];
  int m = (ll + rr) / 2;
  return min(mi(id * 2, l, r, ll, m), mi(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 || bv[id] < va) return -1;
  if (ll == rr) return ll;
  int m = (ll + rr) / 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 || bv[id] < va) return -1;
  if (ll == rr) return ll;
  int m = (ll + rr) / 2;
  int te = lal(id * 2, va, l, r, ll, m);
  if (te >= 0) return te;
  return lal(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 >= l && r >= rr) {
    return upper_bound(aa[id].begin(), aa[id].end(), va) - aa[id].begin();
  }
  int m = (ll + rr) / 2;
  return bel(id * 2, va, l, r, ll, m) + bel(id * 2 + 1, va, l, r, m + 1, rr);
}

int rii[100005], lee[100005];
void init(int N, std::vector<int> H) {
  n = N;
  pv.push_back({-2000000001, -1});
  for (int i = 0; i < N; i++) {
    mama[i] = 2000000001;
    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);
  }
  int te = pv.size();
  if ((pv[te - 1].first > pv[te - 2].first && -1000000001 > pv[te - 1].first) || (pv[te - 1].first < pv[te - 2].first && -1000000001 < pv[te - 1].first)) {
    pv[te - 1] = make_pair(-1000000001, N);
  } else {
    pv.push_back({-1000000001, N});
  }
  te = pv.size();
  priority_queue<pair<int, pair<int, int>>> pq;
  for (int i = 1; i < te; i++) {
    pq.push({-abs(pv[i].first - pv[i - 1].first), {i - 1, i}});
    rii[i - 1] = i;
    lee[i] = i - 1;
  }
  int xx = te / 2;
  while (1) {
    pair<int, pair<int, int>> pin = pq.top();
    pq.pop();
    if (lee[pin.second.first] == -1 || lee[pin.second.second] == -1) continue;
    pq.push({-abs(pv[lee[pin.second.first]].first - pv[rii[pin.second.second]].first), {lee[pin.second.first], rii[pin.second.second]}});
    if (pv[pin.second.first].first > pv[pin.second.second].first) {
      mama[pv[pin.second.first].second] = -pin.first;
    } else {
      mama[pv[pin.second.second].second] = -pin.first;
    }
    xx--;
    if (!xx) break;
    rii[lee[pin.second.first]] = rii[pin.second.second];
    lee[rii[pin.second.second]] = lee[pin.second.first];
    lee[pin.second.first] = -1;
    lee[pin.second.second] = -1;
  }
  build(1, 0, N - 1);
}

int max_towers(int L, int R, int D) {
  int lai = lal(1, D, L, R, 0, n - 1), rai = lar(1, D, L, R, 0, n - 1);
  if (hi[L] == hi[R] || lai == -1) return 1;
  int co = (hi[rai] - hi[lai]) / 2 - bel(1, D - 1, lai, rai, 0, n - 1);
  if (h[lai] - mi(1, L, lai, 0, n - 1) >= D) co++;
  if (h[rai] - mi(1, rai, R, 0, n - 1) >= D) co++;
  return co;
}

Compilation message (stderr)

towers.cpp: In function 'int build(int, int, int)':
towers.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     while (i < aa[id * 2].size() && j < aa[id * 2 + 1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~
towers.cpp:21:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     while (i < aa[id * 2].size() && j < aa[id * 2 + 1].size()) {
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (i < aa[id * 2].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~
towers.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (j < aa[id * 2 + 1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~

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