제출 #1182661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182661		madamadam3	송신탑 (IOI22_towers)	C++20	0 / 100	4042 ms	14408 KiB

towers

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

using namespace std;

typedef long long ll;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

using vi = vector<int>;
using vvi = vector<vi>;

struct SegTree {
  int N, neutral;
  vi st, arr;
  function<int(int, int)> combine;

  SegTree(int _N, vi _arr, function<int(int, int)> _combine, int _neutral) {
    N = _N; arr = _arr; combine = _combine, neutral = _neutral;

    st.assign(4 * N, 0);
    build(0, 0, N);
  } 

  SegTree() : N(0), neutral(0) {};

  int build(int i, int l, int r) {
    if (l + 1 == r) return st[i] = arr[l];
    int m = l + (r - l) / 2;
    return st[i] = combine(build(2 * i + 1, l, m), build(2 * i + 2, m, r));
  }

  int query(int i, int l, int r, int ql, int qr) {
    if (r <= ql || qr <= l) return neutral;
    if (ql <= l && r <= qr) return st[i];

    int m = l + (r - l) / 2;
    return combine(query(2 * i + 1, l, m, ql, qr), query(2 * i + 2, m, r, ql, qr));
  }

  int update(int i, int l, int r, int k, int v) {
    if (!(l <= k && k < r)) return st[i];
    if (l + 1 == r) return st[i] = arr[k] = v;

    int m = l + (r - l) / 2;
    return st[i] = combine(update(2 * i + 1, l, m, k, v), update(2 * i + 2, m, r, k, v));
  }

  int query(int l, int r) {
    return query(0, 0, N, l, r);
  }

  void update(int k, int v) {
    update(0, 0, N, k, v);
  }
};

struct DSU {
  int N;
  vi par, siz, mv;
  set<int> components;

  DSU(int _N, vi _mv) {
    N = _N;
    par.resize(N); iota(par.begin(), par.end(), 0);
    siz.assign(N, 1);
    mv = _mv;
    components = set<int>(all(par));
  }

  DSU() : N(0) {};

  int find_set(int v) {
    if (v == par[v]) return v;
    return par[v] = find_set(par[v]);
  }

  void union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);

    if (a != b) {
      if (siz[a] > siz[b]) {
        siz[a] += siz[b];
        par[b] = a;
        mv[a] = min(mv[b], mv[a]);
        components.erase(b);
      } else {
        siz[b] += siz[a];
        par[a] = b;
        mv[b] = min(mv[b], mv[a]);
        components.erase(a);
      }
    }
  }
};

int n;
vi h, cmp;
SegTree maxST;

function<int(int, int)> mx = [](int a, int b) {return max(a, b);};

int gidx(int v) {
  auto it = lower_bound(all(cmp), v);
  if (it == cmp.end()) return -1;
  else return (int) (it - cmp.begin());
}

/*
  If tower i is connected to tower j, and tower j is connected to tower k (i < m1 < j < m2 < k)
  - tower i and k are connected through either m1 or m2

  dp[i][peak] = largest value of dp[j][!peak] for j > i and h[j] <= h[i] - D
  dp[i][!peak] = 1 + largest value of dp[j][peak] for j > i and h[j] >= h[i] + D
*/

void init(int N, vi H) {
  n = N; h = H;
  maxST = SegTree(n, h, mx, INT_MIN);

  cmp = h;
  sort(all(cmp));
  for (int i = 0; i < n; i++) {
    h[i] = lower_bound(all(cmp), h[i]) - cmp.begin();
  }
}

int max_towers(int L, int R, int D) {
  auto dsu = DSU(n, h);
  vvi DP(2, vi(n, 0));
  auto stPeak = SegTree(n, DP[0], mx, INT_MIN);
  auto stTrough = SegTree(n, DP[1], mx, INT_MIN);

  for (int i = R; i >= L; i--) {
    int height = cmp[h[i]];
    int low = gidx(height - D), high = gidx(height + D);

    bool lowFine = low != -1 && cmp[low] <= height - D, highFine = high != -1 && cmp[high] >= height + D;
    int vP = highFine ? stPeak.query(high, n) : -1;
    int vT = lowFine ? stTrough.query(0, low+1) : -1;

    if (lowFine) {
      stPeak.update(h[i], vT);
    }
    
    if (highFine) {
      stTrough.update(h[i], vP);
    }
  }
  
  return max({1, stPeak.query(0, n), stTrough.query(0, n)});
}

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