Submission #1182617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182617		madamadam3	Radio Towers (IOI22_towers)	C++20	0 / 100	4056 ms	9352 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 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 nA, int nB) {
    int a = find_set(nA);
    int b = find_set(nB);

    if (a != b) {
      cout << "Union of " << nA << " and " << nB << "\n";
      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;
SegTree minST;

/*
  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
*/

void init(int N, vi H) {
  n = N; h = H;
  minST = SegTree(n, h, [](int a, int b) {return max(a, b);}, INT_MIN);
}

int max_towers(int L, int R, int D) {
  // cout << "\n\n----------------------\n";
  int ans = 1; // 1 is always possible
  auto dsu = DSU(n, h);

  for (int i = L; i <= R; i++) {
    int tl = 0;
    int left = i;
    int chmax = INT_MIN;

    for (int right = left + 1; right <= R; right++) {
      bool did = false;
      if (h[left] + D <= chmax && h[right] + D <= chmax) {
        tl++;
        left = right;
        did = true;
      }
      chmax = did ? INT_MIN : max(chmax, h[right]);
    }

    ans = max(ans, tl);
  }
  
  // ans = *max_element(all(dsu.siz));
  // cout << "----------------------\n\n";
  return ans;
}

• 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