Submission #1043011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043011		juicy	Tourism (JOI23_tourism)	C++17	100 / 100	217 ms	26056 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n, m, q;
int tin[N], head[N], sz[N], s[N], c[N], res[N], pr[N];
set<array<int, 3>> st[N];
vector<int> g[N];

void upd(int i, int x) {
  for (; i <= m; i += i & -i) {
    s[i] += x;
  }
}

int qry(int i) {
  int res = 0;
  for (; i; i -= i & -i) {
    res += s[i];
  }
  return res;
}

void dfs(int u) {
  for (int &v : g[u]) {
    if (v == pr[u]) {
      swap(v, g[u].back());
      g[u].pop_back();
      break;
    }
  } 
  sz[u] = 1;
  for (int v : g[u]) {
    pr[v] = u;
    dfs(v);
    sz[u] += sz[v];
  } 
}

int order;

void hld(int u, int h) {
  tin[u] = ++order;
  head[u] = h;
  if (g[u].size()) {
    int x = *max_element(g[u].begin(), g[u].end(), [&](int i, int j) {
      return sz[i] < sz[j];
    });
    hld(x, h);
    for (int v : g[u]) {
      if (v ^ x) {
        hld(v, v);
      }
    }
  }
}

void add(int l, int r, int id, set<array<int, 3>> &st) {
  auto it = st.lower_bound(array<int, 3>{l});
  if (it != st.begin() && (*prev(it))[1] >= l) {
    --it;
  }
  for (; it != st.end() && (*it)[0] <= r; it = st.erase(it)) {
    auto [L, R, c] = *it;
    upd(c, L - R - 1);
    if (L < l) {
      upd(c, l - L);
      st.insert({L, l - 1, c});
    }
    if (R > r) {
      upd(c, R - r);
      st.insert({r + 1, R, c});
    }
  }
  st.insert({l, r, id});
  upd(id, r - l + 1);
}

void upd(int u, int v, int id) {
  for (; head[u] != head[v]; ) {
    if (sz[head[u]] > sz[head[v]]) {
      swap(u, v);
    }
    int h = head[u];
    add(tin[h], tin[u], id, st[h]);
    u = pr[h];
  }
  if (sz[u] < sz[v]) {
    swap(u, v);
  }
  if (tin[u] + 1 <= tin[v]) {
    add(tin[u] + 1, tin[v], id, st[head[u]]);
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> q;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  hld(1, 1);
  for (int i = 1; i <= m; ++i) {
    cin >> c[i];
  }
  vector<array<int, 3>> queries;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    queries.push_back({l, r, i});
  }
  sort(queries.begin(), queries.end(), [&](auto a, auto b) {
    return a[1] < b[1];
  });
  for (int i = 1, j = 0; i <= m; ++i) {
    if (i > 1) {
      upd(c[i - 1], c[i], i);
    } 
    while (j < q && queries[j][1] == i) {
      auto [l, r, id] = queries[j++];
      res[id] = qry(r) - qry(l) + 1;
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41