Submission #1046767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046767		Trent	Radio Towers (IOI22_towers)	C++17	23 / 100	4066 ms	6988 KiB

towers

#include "towers.h"
#include "bits/stdc++.h";
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct pii{int a, b;};

const int MN = 1e5 + 10;
int h[MN], n;
void init(int N, std::vector<int> H) {
  n = N;
  forR(i, N) h[i] = H[i];
}

int l[MN], r[MN], cmax[MN];
struct event{int ti, i, ty;}; // 0: L, 1: i
int bit[MN];
void upd(int i, int to) {
  bit[i] = max(bit[i], to);
}
int qu(int i) {
  int ret = bit[i];
  for(; i >= 0; --i) ret = max(ret, bit[i]);
  return ret;
}
int max_towers(int L, int R, int D) {
  vector<int> mono;
  REP(i, L, R+1) {
    int ind = upper_bound(all(mono), h[i] + D, [](int a, int b){return a > h[b];}) - mono.begin() - 1;
    l[i] = ind == -1 ? L-1 : mono[ind];
    while(!mono.empty() && h[mono.back()] <= h[i]) mono.pop_back();
    mono.push_back(i);
  }
  mono.clear();
  for(int i = R; i >= L; --i) {
    int ind = upper_bound(all(mono), h[i] + D, [](int a, int b){return a > h[b];}) - mono.begin() - 1;
    r[i] = ind == -1 ? R + 1 : mono[ind];
    while(!mono.empty() && h[mono.back()] <= h[i]) mono.pop_back();
    mono.push_back(i);
  }
  vector<event> evs;
  REP(i, L, R+1) {
    evs.push_back({l[i], i, 0});
    evs.push_back({i, i, 1});
  }
  sort(all(evs), [](event& a, event& b){return a.ti < b.ti || a.ti == b.ti && a.ty == 0 && b.ty != 0;});
  for(auto [ti, i, ty] : evs) {
    if(ty == 0) {
      cmax[i] = qu(i) + 1;
    } else {
      upd(r[i] + 1, cmax[i]);
    }
  }
  return qu(MN - 1);
}

Compilation message (stderr)

towers.cpp:2:25: warning: extra tokens at end of #include directive
    2 | #include "bits/stdc++.h";
      |                         ^
towers.cpp: In lambda function:
towers.cpp:52:89: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |   sort(all(evs), [](event& a, event& b){return a.ti < b.ti || a.ti == b.ti && a.ty == 0 && b.ty != 0;});
      |                                                               ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 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