제출 #830712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830712		NeroZein	송신탑 (IOI22_towers)	C++17	23 / 100	4054 ms	3408 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

struct SegTree {
  int n;
  vector<int> seg;
  void init (int n_) {
    n = n_; 
    seg.resize(n * 2 - 1);
    build(); 
  }
  void build(int nd, int l, int r) {
    seg[nd] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    build(nd + 1, l, mid);
    build(rs, mid + 1, r); 
  }
  void build() {
    build(0, 0, n - 1); 
  }
  void upd (int nd, int l, int r, int p, int v) {
    if (l == r) {
      seg[nd] = v;
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (p <= mid) {
      upd(nd + 1, l, mid, p, v);
    } else {
      upd(rs, mid + 1, r, p, v); 
    }
    seg[nd] = max(seg[nd + 1], seg[rs]); 
  }
  void upd(int p, int v) {
    upd(0, 0, n - 1, p, v); 
  }
  int qry (int nd, int l, int r, int s, int e) {
    if (l >= s && r <= e) return seg[nd];
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e);
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e);
      } else {
        return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
      }
    }
  }
  int qry(int s, int e) {
    return qry(0, 0, n - 1, s, e); 
  }
};

vector<int> a; 
vector<int> b; 
SegTree not_matched;
SegTree not_complete;

void init(int N, std::vector<int> H) {
  a = b = H; 
  sort(b.begin(), b.end()); 
  not_matched.init(N); 
  not_complete.init(N); 
}

int get_ind(int value) {
  return upper_bound(b.begin(), b.end(), value) - b.begin() - 1;
}

int get_ind2(int value) {
  return lower_bound(b.begin(), b.end(), value) - b.begin(); 
}

int max_towers(int L, int R, int D) {
  not_complete.build();
  not_matched.build();
  for (int i = L; i <= R; ++i) {
    int match = get_ind(a[i] - D); 
    if (match >= 0) {
      assert(match < (int) a.size()); 
      int best = not_matched.qry(0, match);
      not_complete.upd(get_ind(a[i]), best); 
    }
    int complete = get_ind2(a[i] + D);
    int best = 0;
    if (complete < (int) a.size()) {
      best = not_complete.qry(complete, (int) a.size() - 1); 
    }
    not_matched.upd(get_ind(a[i]), best + 1); 
  }
  return not_matched.seg[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