Submission #795913

#	Time	Username	Problem	Language	Result	Execution time	Memory
795913		erray	Two Currencies (JOI23_currencies)	C++17	30 / 100	294 ms	41444 KiB

currencies

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

template<typename T, typename F = function<T(const T&, const T&)>> 
struct SparseTable {
  vector<vector<T>> a;
  int n;
  F op;
  SparseTable() { }
  SparseTable(vector<T> _a, F _op) : op(_op) {
    n = int(_a.size());
    int lg = 32 - __builtin_clz(n);
    a.resize(lg); 
    a[0] = _a;
    for (int j = 1; j < lg; ++j) {
      int size = n - (1 << j) + 1;
      a[j].resize(size);
      for (int i = 0; i < size; ++i) {
        a[j][i] = op(a[j - 1][i], a[j - 1][i + ((1 << (j - 1)))]);
      }
    }
  }
  T get(int l, int r) {
    assert(l >= 0 && r < n && l <= r);
    int lg = __lg(r - l + 1);
    return op(a[lg][l], a[lg][r + 1 - (1 << lg)]);
  }
};

template<typename T>
struct Fenwick {
  vector<T> tree; 
  int n;
  Fenwick(int _n) : n(_n) {
    tree.resize(n + 1);
  }
  T get(int x) {
    x += 1;
    T res = 0;
    while (x > 0) {
      res += tree[x];
      x -= x & -x;
    }
    return res;
  }
  void modify(int x, T d) {
    x += 1;
    while (x <= n) {
      tree[x] += d;
      x += x & -x;  
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<int> A(N - 1), B(N - 1);
  vector<vector<int>> g(N);
  for (int i = 0; i < N - 1; ++i) {
    cin >> A[i] >> B[i];
    --A[i], --B[i];
    g[A[i]].push_back(i);
    g[B[i]].push_back(i);
  }
  vector<array<int, 2>> C(M);
  for (int i = 0; i < M; ++i) {
    cin >> C[i][1] >> C[i][0];
    --C[i][1];
  } 
  sort(C.begin(), C.end());
  vector<int> S(Q), T(Q), X(Q);
  vector<long long> Y(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> S[i] >> T[i] >> X[i] >> Y[i];
    --S[i], --T[i];
  }
  vector<int> tin(N), tout(N), d(N), tour;
  function<void(int, int)> Dfs = [&](int v, int pr) {
    tin[v] = int(tour.size());
    tour.push_back(v);
    bool leaf = true;
    for (auto id : g[v]) {
      int u = A[id] ^ B[id] ^ v;
      if (u == pr) {
        continue;
      }
      if (A[id] == u) {
        swap(A[id], B[id]);
      }
      d[u] = d[v] + 1;
      Dfs(u, v);
      tout[v] = int(tour.size());
      tour.push_back(v);
      leaf = false;
    }
    if (leaf) {      
      tout[v] = int(tour.size());
      tour.push_back(v);
    }
  };
  Dfs(0, -1);
  debug(d, tour, tin, tout);
  int s = int(tour.size());
  for (int i = 0; i < Q; ++i) {
    if (tin[S[i]] > tin[T[i]]) {
      swap(S[i], T[i]);
    }
  }                    
  for (int i = 0; i < M; ++i) {
    C[i][1] = B[C[i][1]];
  }
  SparseTable st(tour, [&](int x, int y) {
    return d[x] < d[y] ? x :  y;
  }); 
  auto Lca = [&](int x, int y) {
    return (tout[x] >= tin[y] ? x : st.get(tout[x], tin[y]));   
  };
  auto Get = [&]<typename T>(int x, int y, Fenwick<T>& ft) -> T {
    debug(x, y, tout[x], tin[y], Lca(x, y));
    return ft.get(tin[x]) + ft.get(tin[y]) - 2 * ft.get(Lca(x, y));
  };
  auto Modify = [&]<typename T>(int x, int delta, Fenwick<T>& ft) {
    ft.modify(tin[x], delta);  
    ft.modify(tout[x], -delta);  
  };

  debug(C); 
  Fenwick<long long> sum(s);
  int p = 0;
  vector<vector<int>> point(M + 1);
  function<void(vector<int>, int l, int r)> Pbs = [&](vector<int> qs, int l, int r) {
    if (l == r) {
      point[l] = qs;
      return;   
    }
    debug(l, r, qs);
    int mid = 1 + ((l + r) >> 1);
    while (p < mid) {
      Modify(C[p][1], C[p][0], sum);
      ++p;
    }
    while (mid < p) {
      --p;
      Modify(C[p][1], -C[p][0], sum);
    }
    vector<int> left, right;
    for (auto i : qs) {
      (Get(S[i], T[i], sum) > Y[i] ? left : right).push_back(i);
    }
    Pbs(left, l, mid - 1);
    Pbs(right, mid, r);
  };
  vector<int> foo(Q);
  iota(foo.begin(), foo.end(), 0);
  Pbs(foo, 0, M); 
  debug(point);
  Fenwick<int> cnt(s);
  for (int i = 0; i <= M; ++i) {
    for (auto id : point[i]) {
      X[id] += Get(S[id], T[id], cnt);
    }
    if (i < M) {
      Modify(C[i][1], +1, cnt); 
    }   
  }
  debug(X);
  for (int i = 0; i < Q; ++i) {
    debug(S[i], T[i]);
    X[i] -= Get(S[i], T[i], cnt);
  }
  for (int i = 0; i < Q; ++i) {
    cout << max(X[i], -1) << '\n';
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 30 / 30
• Subtask 4: 0 / 32