oj.uz

Submission #626300

# Submission time Handle Problem Language Result Execution time Memory
626300 2022-08-11T11:13:23 Z ITO Radio Towers (IOI22_towers) C++17
4 / 100
 4000 ms 27016 KB 
#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, int>> pq;
  for (int i = 1; i < te; i++) {
    pq.push({-abs(pv[i].first - pv[i - 1].first), i - 1});
    rii[i - 1] = i;
    lee[i] = i - 1;
  }
  int xx = te / 2;
  while (1) {
    pair<int, int> pin = pq.top();
    pq.pop();
    if (lee[pin.second] == -1 || lee[rii[pin.second] == -1]) continue;
    pq.push({-abs(pv[lee[pin.second]].first - pv[rii[rii[pin.second]]].first), lee[pin.second]});
    if (pv[pin.second].first > pv[rii[pin.second]].first) {
      mama[pv[pin.second].second] = -pin.first;
    } else {
      mama[pv[rii[pin.second]].second] = -pin.first;
    }
    xx--;
    if (!xx) break;
    rii[lee[pin.second]] = rii[rii[pin.second]];
    lee[rii[rii[pin.second]]] = lee[pin.second];
    lee[pin.second] = -1;
    lee[rii[pin.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 (L == 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 max(1, co);
}

Compilation message

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 19024 KB Output is correct
2 Correct 938 ms 26980 KB Output is correct
3 Correct 926 ms 26968 KB Output is correct
4 Correct 924 ms 26996 KB Output is correct
5 Correct 829 ms 26964 KB Output is correct
6 Correct 894 ms 26948 KB Output is correct
7 Correct 871 ms 27016 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct
9 Correct 6 ms 9908 KB Output is correct
10 Correct 6 ms 9936 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 9680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 9680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4041 ms 14200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4073 ms 10576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 9680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 19024 KB Output is correct
2 Correct 938 ms 26980 KB Output is correct
3 Correct 926 ms 26968 KB Output is correct
4 Correct 924 ms 26996 KB Output is correct
5 Correct 829 ms 26964 KB Output is correct
6 Correct 894 ms 26948 KB Output is correct
7 Correct 871 ms 27016 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct
9 Correct 6 ms 9908 KB Output is correct
10 Correct 6 ms 9936 KB Output is correct
11 Execution timed out 4058 ms 9680 KB Time limit exceeded
12 Halted 0 ms 0 KB -