Submission #625587

#	Time	Username	Problem	Language	Result	Execution time	Memory
625587		d4xn	Radio Towers (IOI22_towers)	C++17	11 / 100	4072 ms	2240 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>

int n;
vi v;

void init(int N, std::vector<int> H) {
  n = N;
  v.resize(n);
  for (int i = 0; i < n; i++) v[i] = H[i];
}

int max_towers(int L, int R, int D) {
  int l = L;
  int r = R;
  int d = D;

  vii s(r-l+1);
  for (int i = l; i <= r; i++) {
    s[i-l] = make_pair(v[i], i);
  }
  sort(s.begin(), s.end());

  vi ok(n, 0);
  int ans = 0;
  for (int i = 0; i < r-l+1; i++) {
    int h = s[i].first;
    int idx = s[i].second;
    if (ok[idx] == ans) {
      ans++;

      int mx;
      if (idx+1 < n) mx = v[idx+1];
      for (int j = idx+2; j <= r; j++) {
        if (max(h, v[j]) + d <= mx) ok[j]++;
        mx = max(mx, v[j]);
      }

      if (idx-1 >= 0) mx = v[idx-1];
      for (int j = idx-2; j >= l; j--) {
        if (max(h, v[j]) + d <= mx) ok[j]++;
        mx = max(mx, v[j]);
      }
    }
  }
  return ans;
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:38:11: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |       int mx;
      |           ^~

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