제출 #630193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630193		abeker	송신탑 (IOI22_towers)	C++17	73 / 100	4059 ms	60240 KiB

towers

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

const int INF = INT_MAX;

class RMQ {
  int offset;
  vector <int> tour;
public:
  RMQ(vector <int> vals) {
    for (offset = 1; offset < vals.size(); offset *= 2);
    tour.resize(2 * offset);
    for (int i = 0; i < offset; i++)
      tour[i + offset] = i < vals.size() ? vals[i] : INF;
    for (int i = offset - 1; i; i--)
      tour[i] = min(tour[2 * i], tour[2 * i + 1]);
  }
  RMQ() {}
  int query(int x, int lo, int hi, int from, int to) const {
    if (lo >= to || hi <= from)
      return INF;
    if (lo >= from && hi <= to)
      return tour[x];
    int mid = (lo + hi) / 2;
    return min(query(2 * x, lo, mid, from, to), query(2 * x + 1, mid, hi, from, to));
  }
  int query(int from, int to) const {
    return query(1, 0, offset, from, to);
  }
};

class Orthogonal {
  int offset;
  vector <vector <int>> tour;
public:
  Orthogonal(vector <int> vals) {
    for (offset = 1; offset < vals.size(); offset *= 2);
    tour.resize(2 * offset);
    for (int i = 1; i < vals.size(); i++)
      tour[i + offset].push_back(vals[i]);
    for (int i = offset - 1; i; i--) {
      tour[i].resize(tour[2 * i].size() + tour[2 * i + 1].size());
      merge(tour[2 * i].begin(), tour[2 * i].end(), tour[2 * i + 1].begin(), tour[2 * i + 1].end(), tour[i].begin());
    }
  }
  Orthogonal() {}
  int query(int x, int lo, int hi, int from, int to, int val) {
    if (lo >= to || hi <= from)
      return 0;
    if (lo >= from && hi <= to)
      return lower_bound(tour[x].begin(), tour[x].end(), val) - tour[x].begin();
    int mid = (lo + hi) / 2;
    return query(2 * x, lo, mid, from, to, val) + query(2 * x + 1, mid, hi, from, to, val);
  }
  int query(int from, int to, int val) {
    return query(1, 0, offset, from, to, val);
  }
};

int N, lg;
vector <int> H;
vector <int> lb, ub;
vector <vector <int>> lft, rig;
Orthogonal count_lb, count_ub;
RMQ mini;

void init(int n, vector <int> h) {
  N = n;
  H.resize(N + 2);
  H[0] = H[N + 1] = INF;
  for (int i = 1; i <= N; i++)
    H[i] = h[i - 1];
  while (1 << lg < N)
    lg++;
  lft.resize(N + 2, vector <int> (lg + 1));
  rig.resize(N + 2, vector <int> (lg + 1));
  stack <int> s;
  s.push(0);
  for (int i = 1; i <= N; i++) {
    while (H[s.top()] < H[i])
      s.pop();
    lft[i][0] = s.top();
    s.push(i);
  }
  s = stack <int> ();
  s.push(N + 1);
  for (int i = N; i; i--) {
    while (H[s.top()] < H[i])
      s.pop();
    rig[i][0] = s.top();
    s.push(i);
  }
  rig[N + 1] = vector <int> (lg + 1, N + 1);
  for (int j = 1; j <= lg; j++)
    for (int i = 1; i <= N; i++) {
      lft[i][j] = lft[lft[i][j - 1]][j - 1];
      rig[i][j] = rig[rig[i][j - 1]][j - 1];
    }
  mini = RMQ(H);
  lb.resize(N + 1);
  ub.resize(N + 1);
  for (int i = 1; i <= N; i++) {
    int tmp = mini.query(lft[i][0] + 1, rig[i][0]);
    lb[i] = H[i] - tmp;
    ub[i] = min(H[lft[i][0]], H[rig[i][0]]) - tmp;
  }
  count_lb = Orthogonal(lb);
  count_ub = Orthogonal(ub);
}

int jump(int x, int k, const vector <vector <int>> &anc) {
  for (int i = 0; i <= lg; i++)
    if (k >> i & 1)
      x = anc[x][i];
  return x;
}

int max_towers(int l, int r, int d) {
  l += 1;
  r += 1;
  int smaller_lb = count_lb.query(l, r + 1, d);
  int smaller_ub = count_ub.query(l, r + 1, d);
  int lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(l, mid, rig);
    if (rig[node][0] <= r && lb[node] < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_lb -= lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(r, mid, lft);
    if (lft[node][0] >= l && lb[node] < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_lb -= lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(l, mid, rig);
    if (rig[node][0] <= r && H[node] - mini.query(l, rig[node][0]) < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_lb += lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(r, mid, lft);
    if (lft[node][0] >= l && H[node] - mini.query(lft[node][0] + 1, r + 1) < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_lb += lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(l, mid, rig);
    if (rig[node][0] <= r && ub[node] < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_ub -= lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(r, mid, lft);
    if (lft[node][0] >= l && ub[node] < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_ub -= lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(l, mid, rig);
    if (rig[node][0] <= r && H[rig[node][0]] - mini.query(l, rig[node][0]) < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_ub += lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(r, mid, lft);
    if (lft[node][0] >= l && H[lft[node][0]] - mini.query(lft[node][0] + 1, r + 1) < d)
      lo = mid + 1;
    else
      hi = mid;
  }
  smaller_ub += lo;
  lo = 0, hi = r - l + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int node = jump(l, mid, rig);
    if (rig[node][0] <= r)
      lo = mid + 1;
    else
      hi = mid;
  }
  int arg_max = jump(l, lo, rig);
  smaller_lb -= lb[arg_max] < d;
  smaller_lb += H[arg_max] - mini.query(l, r + 1) < d;
  smaller_ub -= ub[arg_max] < d;
  return smaller_lb - smaller_ub;
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In constructor 'RMQ::RMQ(std::vector<int>)':
towers.cpp:12:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (offset = 1; offset < vals.size(); offset *= 2);
      |                      ~~~~~~~^~~~~~~~~~~~~
towers.cpp:15:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |       tour[i + offset] = i < vals.size() ? vals[i] : INF;
      |                          ~~^~~~~~~~~~~~~
towers.cpp: In constructor 'Orthogonal::Orthogonal(std::vector<int>)':
towers.cpp:38:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (offset = 1; offset < vals.size(); offset *= 2);
      |                      ~~~~~~~^~~~~~~~~~~~~
towers.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 1; i < vals.size(); i++)
      |                     ~~^~~~~~~~~~~~~

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