Submission #702222

#	Time	Username	Problem	Language	Result	Execution time	Memory
702222		dykw	Radio Towers (IOI22_towers)	C++17	17 / 100	1004 ms	35604 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

constexpr int MaxN = 100000;
constexpr int LogN = 16;
constexpr int Inf = 1E9;

namespace RMQ {
  int st[LogN + 1][MaxN];
  
  void build(vector<int> &H) {
    int N = H.size();
    for (int i = 0; i < N; ++i) {
      st[0][i] = H[i];
    }
    for (int i = 1; (1 << i) <= N; ++i) {
      for (int j = 0; j + (1 << i) - 1 < N; ++j) {
        st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  
  int ask(int l, int r) {
    if (l > r) {
      return -1;
    }
    int k = __lg(r - l + 1);
    return max(st[k][l], st[k][r - (1 << k) + 1]);
  }
}

namespace T {
  int val_l[MaxN * 4], val_r[MaxN * 4];
  
  void build(int l, int r, int x, const vector<int> &vl, const vector<int> &vr) {
    if (l == r) {
      val_l[x] = vl[l];
      val_r[x] = vr[l];
      return;
    }
    int mid = (l + r) / 2;
    build(l, mid, x * 2, vl, vr);
    build(mid + 1, r, x * 2 + 1, vl, vr);
    val_l[x] = max(val_l[x * 2], val_l[x * 2 + 1]);
    val_r[x] = max(val_r[x * 2], val_r[x * 2 + 1]);
  }
  
  int find_l(int l, int r, int ql, int qr, int delta, int x) {
    if (val_r[x] < delta) {
      return MaxN;
    }
    if (l == r) {
      return l;
    }
    int mid = (l + r) / 2;
    if (ql <= l && r <= qr) {
      if (val_r[x * 2] >= delta) {
        return find_l(l, mid, ql, qr, delta, x * 2);
      } else {
        return find_l(mid + 1, r, ql, qr, delta, x * 2 + 1);
      }
    }
    if (ql > mid) {
      return find_l(mid + 1, r, ql, qr, delta, x * 2 + 1);
    } else if (qr <= mid) {
      return find_l(l, mid, ql, qr, delta, x * 2);
    } else {
      int res = find_l(l, mid, ql, qr, delta, x * 2);
      if (res != MaxN) {
        return res;
      } else {
        return find_l(mid + 1, r, ql, qr, delta, x * 2 + 1);
      }
    }
  }
  
  int find_r(int l, int r, int ql, int qr, int delta, int x) {
    if (val_l[x] < delta) {
      return -1;
    }
    if (l == r) {
      return l;
    }
    int mid = (l + r) / 2;
    if (ql <= l && r <= qr) {
      if (val_l[x * 2 + 1] >= delta) {
        return find_r(mid + 1, r, ql, qr, delta, x * 2 + 1);
      } else {
        return find_r(l, mid, ql, qr, delta, x * 2);
      }
    }
    if (ql > mid) {
      return find_r(mid + 1, r, ql, qr, delta, x * 2 + 1);
    } else if (qr <= mid) {
      return find_r(l, mid, ql, qr, delta, x * 2);
    } else {
      int res = find_r(mid + 1, r, ql, qr, delta, x * 2 + 1);
      if (res != -1) {
        return res;
      } else {
        return find_r(l, mid, ql, qr, delta, x * 2);
      }
    }
  }
}

namespace PerT {
  struct Node {
    int l, r;
    int v;
    Node() : l(), r(), v() {}
  };
  vector<Node> t(1);
  
  int insert(int l, int r, int p, int x) {
    int y = t.size();
    t.push_back(t[x]);
    ++t[y].v;
    if (l == r) {
      return y;
    }
    int mid = (l + r) / 2;
    if (p <= mid) {
      t[y].l = insert(l, mid, p, t[x].l);
    } else {
      t[y].r = insert(mid + 1, r, p, t[x].r);
    }
    return y;
  }
  
  int ask(int l, int r, int ql, int qr, int x, int y) {
    if (ql <= l && r <= qr) {
      return t[y].v - t[x].v;
    }
    int mid = (l + r) / 2;
    if (ql > mid) {
      return ask(mid + 1, r, ql, qr, t[x].r, t[y].r);
    } else if (qr <= mid) {
      return ask(l, mid, ql, qr, t[x].l, t[y].l);
    } else {
      return ask(l, mid, ql, qr, t[x].l, t[y].l) + ask(mid + 1, r, ql, qr, t[x].r, t[y].r);
    }
  }
}

int N, root[MaxN + 1];

void init(int N_, vector<int> H) {
  N = N_;
  RMQ::build(H);
  
  vector<int> stk(N + 1);
  int top = 0;
  
  vector<int> l(N), r(N);
  for (int i = 0; i < N; ++i) {
    while (top && H[stk[top]] > H[i]) {
      --top;
    }
    l[i] = top ? RMQ::ask(stk[top] + 1, i - 1) : Inf;
    if (top && l[i] > 0) {
      l[i] -= H[i];
    }
    stk[++top] = i;
  }
  top = 0;
  for (int i = N - 1; i >= 0; --i) {
    while (top && H[stk[top]] > H[i]) {
      --top;
    }
    r[i] = top ? RMQ::ask(i + 1, stk[top] - 1) : Inf;
    if (top && r[i] > 0) {
      r[i] -= H[i];
    }
    stk[++top] = i;
  }
  
  T::build(0, N - 1, 1, l, r);
  for (int i = 0; i < N; ++i) {
    if (l[i] == -1 || r[i] == -1) {
      root[i + 1] = root[i];
      continue;
    }
    root[i + 1] = PerT::insert(0, Inf, min(l[i], r[i]), root[i]);
  }
}

int max_towers(int L, int R, int D) {
  int avail_l = T::find_l(L, N - 1, 0, N - 1, D, 1);
  int avail_r = T::find_r(0, R, 0, N - 1, D, 1);
  if (avail_r - avail_l <= 1) {
    return 1;
  }
  return PerT::ask(0, Inf, D, Inf, root[avail_l + 1], root[avail_r]) + 2;
}

#ifdef LOCAL_GRADER

int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int L, R, D;
    assert(3 == scanf("%d %d %d", &L, &R, &D));
    printf("%d\n", max_towers(L, R, D));
  }
  return 0;
}

#endif

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