Submission #1223836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223836		trimkus	Radio Towers (IOI22_towers)	C++20	0 / 100	4091 ms	2224 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<int> R, L;
int idx;
int N;
void init(int _N, std::vector<int> _H) {
  N = _N;
  a = _H;
  // cerr << "H = ";
  // for (auto& u : a) {
  //   cerr << u << " ";
  // }
  // cerr << "\n";
}

int max_towers(int l, int r, int D) {
    int res = 1;
    vector<pair<int, int>> tw;
    vector<int> idx;
    idx.push_back(l - 1);
    for (int i = l + 1; i < r; ++i) {
      if (a[i - 1] < a[i] && a[i] > a[i + 1]) {
        tw.push_back({a[i], tw.size()});
        idx.push_back(i);
      }
    }
    idx.push_back(r + 1);
    sort(rbegin(tw), rend(tw));
    vector<int> mn((int)tw.size() + 1, 1e9 + 1);
    int ptr = 0;
    for (int i = 1; i < (int)idx.size(); ++i) {
        int st = idx[i - 1] + 1;
        int en = idx[i] - 1;
        // cerr << "[" << st << " , " << en << "]: ";
        for (int j = st; j <= en; ++j) {
          // cerr << j << " = " << a[j] << " , ";
            mn[ptr] = min(mn[ptr], a[j]);
        }
        // cerr << "\n";
        ptr += 1;
    }
    // cerr << "mn = ";
    // for (auto& u : mn) {
    //   cerr << u << " ";
    // }
    // cerr << "\n";
    // cerr << "tw =\n";
    // for (auto& [u, i] : tw) {
    //   cerr << u << " " << i << "\n";
    // }
    // cerr << "\n";
    priority_queue<pair<int, int>> pq;
    vector<bool> active(tw.size() + 1);
    int now = 0;
    for (auto& [u, i] : tw) {
      while (pq.size() && pq.top().first + D > u) {
          int j = pq.top().second;
          if (active[j]) {
            active[j] = false;
            now -= 1;
          }
          pq.pop();
      }
      res = max(res, now);
      if (mn[i] + D <= u) {
        if (!active[i]) {
          active[i] = true;
          now += 1;
          pq.push({mn[i], i});
        }
      }
      if (mn[i + 1] + D <= u) {
        if (!active[i + 1]) {
          active[i + 1] = true;
          now += 1;
          pq.push({mn[i + 1], i + 1});
        }
      }
    }
    return res;
}

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