Submission #1036400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036400		juicy	Two Currencies (JOI23_currencies)	C++17	100 / 100	892 ms	33860 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 5, LG = 17;

int n, m, q;
int t[N], res[N], pr[LG][N], dep[N], ord[N], G[N], A[N], B[N], tin[N], tout[N], a[N], ver[N];
long long s[N], sum[N];
array<int, 2> roads[N];
vector<int> g[N];

int timer;

void dfs(int u) {
  tin[u] = ++timer;
  for (int v : g[u]) {
    if (v != pr[0][u]) {
      pr[0][v] = u;
      for (int j = 1; j < LG; ++j) {
        pr[j][v] = pr[j - 1][pr[j - 1][v]];
      }
      dep[v] = dep[u] + 1; 
      dfs(v);
    }
  }
  tout[u] = timer;
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[v]) {
      u = pr[j][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int j = LG - 1; ~j; --j) {
    if (pr[j][u] != pr[j][v]) {
      u = pr[j][u], v = pr[j][v];
    }
  }
  return pr[0][u];
}

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

void upd(int l, int r, long long x) {
  upd(l, x);
  upd(r + 1, -x);
}

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

long long get(int u, int v) {
  return qry(tin[u]) + qry(tin[v]) - 2 * qry(tin[lca(u, v)]);
}

long long get(int id) {
  return get(A[id], B[id]);
}

void add(int p, int x) {
  int u = ver[ord[p]];
  if (u) {
    upd(tin[u], tout[u], x * a[ord[p]]);
  }
}

void add(int p) {
  int u = ver[ord[p]];
  if (u) {
    upd(tin[u], tout[u], 1);
  }
}

int L = 1, R = 0;

void shift(int a, int b) {
  while (R < b) {
    add(++R, 1);
  }
  while (L > a) {
    add(--L, 1);
  }
  while (R > b) {
    add(R--, -1);
  } 
  while (L < a) {
    add(L++, -1);
  }
}

void dc(int l, int r, vector<int> Queries) {
  if (l == r) {
    for (int id : Queries) {
      t[id] = l;
    }
    return;
  }
  int md = (l + r) / 2;
  vector<int> lt, rt;
  shift(l, md);
  for (int id : Queries) {
    auto x = get(id);
    if (sum[id] > x) {
      rt.push_back(id);
      sum[id] -= x;
    } else {
      lt.push_back(id);
    }
  }
  dc(l, md, lt);
  dc(md + 1, r, rt);
}

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;
    roads[i] = {u, v};
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  for (int i = 1; i <= m; ++i) {
    int p, x; cin >> p >> x;
    auto [u, v] = roads[p];
    if (dep[u] < dep[v]) {
      swap(u, v);
    }
    ver[i] = u;
    a[i] = x;
  }
  iota(ord + 1, ord + m + 1, 1);
  sort(ord + 1, ord + m + 1, [&](int u, int v) {
    return a[u] > a[v];
  });
  for (int i = 1; i <= q; ++i) {
    long long X; cin >> A[i] >> B[i] >> G[i] >> X;
    sum[i] -= X;
  }
  shift(1, m);
  for (int i = 1; i <= q; ++i) {
    sum[i] += get(i);
  }
  vector<int> Queries(q);
  iota(Queries.begin(), Queries.end(), 1);
  dc(0, m + 1, Queries);
  shift(0, 0);
  vector<array<int, 2>> qu;
  for (int i = 1; i <= q; ++i) {
    if (t[i] == m + 1) {
      res[i] = -1;
    } else if (t[i]) {
      qu.push_back({t[i], i});
    } else {
      res[i] = G[i];
    }
  }
  sort(qu.begin(), qu.end());
  for (int i = 1, j = 0; i <= m; ++i) {
    add(i);
    while (j < qu.size() && qu[j][0] == i) {
      int id = qu[j][1];
      res[id] = get(id);
      if (res[id] > G[id]) {
        res[id] = -1;
      } else {
        res[id] = G[id] - res[id];
      }
      ++j;  
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:186:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     while (j < qu.size() && qu[j][0] == i) {
      |            ~~^~~~~~~~~~~

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