Submission #855779

#	Time	Username	Problem	Language	Result	Execution time	Memory
855779		tvladm2009	Two Currencies (JOI23_currencies)	C++17	0 / 100	3 ms	19548 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 7;
const int K = 20;
const int B = 317;
int n;
int m;
int q;
vector<int> g[N];
pair<int, int> edges[N];
int dep[N];
int par[N];
int l[N];
int r[N];
int tab[K][N];
int tt = 0;
pair<int, int> updates[N];
ll sumToRoot[B][N];
ll prefSum[B][N];
int countToRoot[B][N];
int prefCount[B][N];

int get_bucket(int x) {
  return (x - 1) / B + 1;
}

struct segtree {
  int n;
  vector<ll> tree;
  vector<ll> lazy;

  void init(int nn) {
    n = nn;
    tree.resize(4 * n + 1);
    lazy.resize(4 * n + 1);
    for (int i = 1; i <= 4 * n; i++) {
      tree[i] = 0;
      lazy[i] = 0;
    }
  }

  void push(int v, int tl, int tr) {
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    tree[v] += lazy[v];
    lazy[v] = 0;
  }

  void applyRange(int v, int tl, int tr, int x, int y, ll val) {
    push(v, tl, tr);
    if (x <= tl && tr <= y) {
      lazy[v] += val;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    if (x <= tm) {
      applyRange(2 * v, tl, tm, x, min(tm, y), val);
    }
    if (tm + 1 <= y) {
      applyRange(2 * v + 1, tm + 1, tr, max(x, tm + 1), y, val);
    }
    push(2 * v, tl, tm);
    push(2 * v + 1, tm + 1, tr);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
  }

  ll force(int v, int tl, int tr, int x, int y) {
    push(v, tl, tr);
    if (x <= tl && tr <= y) {
      return tree[v];
    }
    int tm = (tl + tr) / 2;
    if (x <= tm && y <= tm) {
      return force(2 * v, tl, tm, x, y);
    } else if (tm + 1 <= x && tm + 1 <= y) {
      return force(2 * v + 1, tm + 1, tr, x, y);
    } else {
      return force(2 * v, tl, tm, x, tm) + force(2 * v + 1, tm + 1, tr, tm + 1, tr);
    }
  }
};

void build(int a, int p = 0) {
  l[a] = ++tt;
  tab[0][a] = p;
  for (int k = 1; k < K; k++) {
    tab[k][a] = tab[k - 1][tab[k - 1][a]];
  }
  for (auto &b : g[a]) {
    if (b != p) {
      par[b] = a;
      dep[b] = dep[a] + 1;
      build(b, a);
    }
  }
  r[a] = tt;
}

int lca(int x, int y) {
  if (dep[x] < dep[y]) {
    swap(x, y);
  }
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) >= dep[y]) {
      x = tab[k][x];
    }
  }
  if (x == y) {
    return x;
  }
  for (int k = K - 1; k >= 0; k--) {
    if (tab[k][x] != tab[k][y]) {
      x = tab[k][x];
      y = tab[k][y];
    }
  }
  return tab[0][x];
}

bool is_ancestor(int x, int y) {
  return l[x] <= l[y] && r[y] <= r[x];
}

ll getToRoot(int when, int node) {
  if (node == 0) {
    return 0;
  }
  int bucket = get_bucket(when) - 1;
  ll sol = prefSum[bucket][node];
  for (int i = B * bucket + 1; i <= when; i++) {
    ll val = updates[i].first;
    int x = updates[i].second;
    if (is_ancestor(x, node)) {
      sol += val;
    }
  }
  return sol;
}

ll get_sum(int when, int x, int y) {
  int z = lca(x, y);
  return getToRoot(when, x) + getToRoot(when, y) - 2 * getToRoot(when, z);
}

ll getToRoot2(int when, int node) {
  if (node == 0) {
    return 0;
  }
  int bucket = get_bucket(when) - 1;
  ll sol = prefCount[bucket][node];
  for (int i = B * bucket + 1; i <= when; i++) {
    int x = updates[i].second;
    if (is_ancestor(x, node)) {
      sol++;
    }
  }
  return sol;
}

ll get_count(int when, int x, int y) {
  int z = lca(x, y);
  return getToRoot2(when, x) + getToRoot2(when, y) - 2 * getToRoot2(when, z);
}

struct T {
  int s;
  int t;
  int x;
  ll y;
  int low;
  int high;
  int mid;
  int sol;
  int id;
};

vector<T> queries;
int print[N];

void get_moments() {
  int mm = m;
  while (m > 0) {
    m /= 2;
    int k = 0;
    vector<T> new_queries, others;
    while (k < (int) queries.size()) {
      int now = get_sum(queries[k].mid, queries[k].s, queries[k].t);
      if (now <= queries[k].y) {
        queries[k].sol = queries[k].mid;
        queries[k].low = queries[k].mid;
        queries[k].mid = (queries[k].low + queries[k].high) / 2;
        others.push_back(queries[k]);
      } else {
        queries[k].high = queries[k].mid + 1;
        queries[k].mid = (queries[k].low + queries[k].high) / 2;
        new_queries.push_back(queries[k]);
      }
      k++;
    }
    for (auto &it : others) {
      new_queries.push_back(it);
    }
    others.clear();
    queries = new_queries;
  }
  m = mm;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

/// freopen("input.txt", "r", stdin);

  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
    edges[i] = {x, y};
  }
  build(1);
  for (int i = 1; i <= m; i++) {
    ll road, val;
    cin >> road >> val;
    int x = edges[road].first;
    int y = edges[road].second;
    if (dep[x] < dep[y]) {
      swap(x, y);
    }
    updates[i] = {val, x};
  }
  sort(updates + 1, updates + m + 1);


  { /// for sum
    for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
      segtree tree;
      tree.init(n);
      for (int i = (bucket - 1) * B + 1; i <= bucket * B; i++) {
        ll val = updates[i].first;
        int x = updates[i].second;
        if (x != 0) {
          tree.applyRange(1, 1, n, l[x], r[x], val);
        }
      }
      for (int i = 1; i <= n; i++) {
        sumToRoot[bucket][i] = tree.force(1, 1, n, l[i], l[i]);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
        prefSum[bucket][i] = prefSum[bucket - 1][i] + sumToRoot[bucket][i];
      }
    }
  }
  { /// for cnt
    for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
      segtree tree;
      tree.init(n);
      for (int i = (bucket - 1) * B + 1; i <= bucket * B; i++) {
        int x = updates[i].second;
        if (x != 0) {
          tree.applyRange(1, 1, n, l[x], r[x], 1);
        }
      }
      for (int i = 1; i <= n; i++) {
        countToRoot[bucket][i] = tree.force(1, 1, n, l[i], l[i]);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
        prefCount[bucket][i] = prefCount[bucket - 1][i] + countToRoot[bucket][i];
      }
    }
  }

  for (int i = 0; i < q; i++) {
    T aux;
    cin >> aux.s >> aux.t >> aux.x >> aux.y;
    aux.low = 1;
    aux.high = m;
    aux.mid = (m + 1) / 2;
    aux.sol = 0;
    aux.id = i + 1;
    queries.push_back(aux);
  }
  get_moments();
  for (int iq = 0; iq < q; iq++) {
    int s = queries[iq].s;
    int t = queries[iq].t;
    int x = queries[iq].x;
    ll y = queries[iq].y;

    int sol = queries[iq].sol;
    int z = lca(s, t);
    int payed = get_count(sol, s, t);
    int total = get_count(m, s, t);
    int keep = x - (total - payed);
    if (keep < 0) {
      keep = -1;
    }
    print[queries[iq].id] = keep;
  }
  for (int i = 1; i <= q; i++) {
    cout << print[i] << "\n";
  }
  return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:299:8: warning: unused variable 'y' [-Wunused-variable]
  299 |     ll y = queries[iq].y;
      |        ^
currencies.cpp:302:9: warning: unused variable 'z' [-Wunused-variable]
  302 |     int z = lca(s, t);
      |         ^

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