제출 #1224460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224460		trimkus	Radio Towers (IOI22_towers)	C++20	14 / 100	261 ms	5076 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<int> R, L;
int idx;
int N;
const int MAXN = 2e5;
vector<int> ps;
struct RMQ {
  vector<int> tree;
  int n;
  RMQ(int n) {
    this->n = n;
    tree = vector<int>(4 * n);
  }
  void update(int i, int l, int r, int qp, int val) {
    if (l == r) {
      tree[i] = val;
      return;
    }
    int m = (l + r) / 2;
    if (qp <= m) update(i * 2, l, m, qp, val);
    else update(i * 2 + 1, m + 1, r, qp, val);
    tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
  }
  void update(int qp, int val) {
    update(1, 1, n, qp, val);
  }
  int query(int i, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) {
      return tree[i];
    }
    int m = (l + r) / 2;
    return max(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
  }
  int query(int ql, int qr) {
    return query(1, 1, n, ql, qr);
  }
} seg(MAXN + 1);

void init(int _N, std::vector<int> _H) {
  N = _N;
  a.push_back(0);
  for (int i = 1; i <= N; ++i) {
    a.push_back(_H[i - 1]);
  }
  ps = vector<int>(N + 1);
  for (int i = 2; i <= N - 1; ++i) {
      if (a[i - 1] > a[i] && a[i] < a[i + 1]) {
        ps[i] += 1;
      }
  }
  for (int i = 1; i <= N; ++i) {
    ps[i] += ps[i - 1];
  }
}

int max_towers(int l, int r, int D) {
  l += 1; 
  int res = 0;
  if (r >= l) {
    res += ps[r] - ps[l];
    r += 1;
    if (l + 1 <= r) {
        res += (a[l] < a[l + 1]);
    }
    if (r - 1 >= l) {
      res += (a[r] < a[r - 1]);
    }
    res = max(res, 1);
  }
  else {
    res = 1;
  }
  return res;
}

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