제출 #1199805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199805		abczz	송신탑 (IOI22_towers)	C++20	100 / 100	750 ms	67508 KiB

towers

#include "towers.h"
#include <iostream>
#include <vector>
#include <array>
#include <map>
#define ll long long

using namespace std;

array<ll, 2> R[100000];
ll X[400000];
struct SegTree{
  vector <ll> A;
  ll mn[400000], mx[400000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      mn[id] = mx[id] = A[l];
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    mn[id] = min(mn[id*2], mn[id*2+1]);
    mx[id] = max(mx[id*2], mx[id*2+1]);
  }
  ll rhsmaxid(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql || mx[id] < w || ql > qr) return 1e18;
    else if (ql <= l && r <= qr) {
      if (l == r) return l;
      ll mid = (l+r)/2;
      if (mx[id*2] >= w) return rhsmaxid(id*2, l, mid, ql, qr, w);
      else return rhsmaxid(id*2+1, mid+1, r, ql, qr, w);
    }
    ll mid = (l+r)/2;
    ll res = rhsmaxid(id*2, l, mid, ql, qr, w);
    if (res != 1e18) return res;
    else return rhsmaxid(id*2+1, mid+1, r, ql, qr, w);
  }
  ll lhsmaxid(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql || mx[id] < w || ql > qr) return -1e18;
    else if (ql <= l && r <= qr) {
      if (l == r) return l;
      ll mid = (l+r)/2;
      if (mx[id*2+1] >= w) return lhsmaxid(id*2+1, mid+1, r, ql, qr, w);
      else return lhsmaxid(id*2, l, mid, ql, qr, w);
    }
    ll mid = (l+r)/2;
    ll res = lhsmaxid(id*2+1, mid+1, r, ql, qr, w);
    if (res != -1e18) return res;
    else return lhsmaxid(id*2, l, mid, ql, qr, w);
  }
  ll querymin(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql || ql > qr) return 1e18;
    else if (ql <= l && r <= qr) return mn[id];
    ll mid = (l+r)/2;
    return min(querymin(id*2, l, mid, ql, qr), querymin(id*2+1, mid+1, r, ql, qr));
  }
}ST, ST2;

struct PersistentSegTree{
  struct Node{
    ll val;
    ll chl;
    ll chr;
  };
  vector <Node> st;
  ll getNew() {
    st.push_back({0, -1, -1});
    return (ll)st.size()-1;
  }
  void update(ll id, ll nid, ll l, ll r, ll q) {
    if (l == r) {
      st[nid].val = (id == -1 ? 0 : st[id].val) + 1;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) {
      st[nid].chl = getNew(), st[nid].chr = (id == -1 ? -1 : st[id].chr);
      update((id == -1 ? -1 : st[id].chl), st[nid].chl, l, mid, q);
    }
    else {
      st[nid].chl = (id == -1 ? -1 : st[id].chl), st[nid].chr = getNew();
      update((id == -1 ? -1 : st[id].chr), st[nid].chr, mid+1, r, q);
    }
    st[nid].val = (st[nid].chl == -1 ? 0 : st[st[nid].chl].val) + (st[nid].chr == -1 ? 0 : st[st[nid].chr].val);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql || id == -1) return 0;
    else if (ql <= l && r <= qr) return st[id].val;
    ll mid = (l+r)/2;
    return query(st[id].chl, l, mid, ql, qr) + query(st[id].chr, mid+1, r, ql, qr);
  }
}PST;
vector <ll> rt;
map <ll, ll> mp;
vector <ll> H, Z;
ll n;
void init(int N, std::vector<int> height) {
  n = N;
  for (auto u : height) {
    H.push_back(u);
    ST.A.push_back(u);
  }
  ST.build(1, 0, N-1);
  for (int i=0; i<N; ++i) {
    R[i] = {ST.lhsmaxid(1, 0, N-1, 0, i-1, H[i]), ST.rhsmaxid(1, 0, N-1, i+1, N-1, H[i])};
    X[i] = max(0LL, H[i] - max(ST.querymin(1, 0, N-1, max(0LL, R[i][0]+1), i), (ST.querymin(1, 0, N-1, i, min((ll)N-1, R[i][1]-1)))));
    ++mp[X[i]];
    ST2.A.push_back(X[i]);
  }
  ll k = 0;
  for (auto [x, y] : mp) {
    mp[x] = k++;
  }
  ST2.build(1, 0, N-1);
  rt.push_back(PST.getNew());
  for (int i=0; i<N; ++i) {
    auto nrt = PST.getNew();
    PST.update(rt.back(), nrt, 0, mp.size()-1, mp[X[i]]);
    rt.push_back(nrt);
  }
  return;
}

bool check(ll u, ll l, ll r, ll d) {
  if (u == 1e18 || u == -1e18) return 0;
  auto res = max(ST.querymin(1, 0, n-1, max(l, R[u][0]+1), u), (ST.querymin(1, 0, n-1, u, min(r, R[u][1]-1))));
  if (H[u] >= res+d) return 1;
  else return 0;
}
int max_towers(int L, int R, int D) {
  ll ql = ST2.rhsmaxid(1, 0, n-1, L, R, D);
  if (!check(ql, L, R, D)) {
    ql = ST2.rhsmaxid(1, 0, n-1, ql+1, R, D);
    if (!check(ql, L, R, D)) return 1;
  }
  ll qr = ST2.lhsmaxid(1, 0, n-1, L, R, D);
  if (!check(qr, L, R, D)) {
    qr = ST2.lhsmaxid(1, 0, n-1, L, qr-1, D);
    if (!check(qr, L, R, D)) return 1;
  }
  if (ql == qr) return 2;
  auto it = mp.lower_bound(D);
  ll f = 3 + PST.query(rt[qr], 0, mp.size()-1, it->second, mp.size()-1) - PST.query(rt[ql+1], 0, mp.size()-1, it->second, mp.size()-1);
  return f;
}

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