Submission #941458

#	Time	Username	Problem	Language	Result	Execution time	Memory
941458		TAhmed33	Two Currencies (JOI23_currencies)	C++98	100 / 100	1841 ms	66952 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
struct SegmentTree {
    ll tree[MAXN << 1];
    void init () {
        for (int i = 1; i < MAXN; i++) tree[i] = 0;
    }
    void update (ll pos, ll val) {
        for (; pos < MAXN; pos += pos & (-pos)) tree[pos] += val;
    }
    ll get (ll x) {
        ll sum = 0;
        for (; x; x -= x & (-x)) sum += tree[x];
        return sum;
    }
    ll get (ll l, ll r) {
        return get(r) - get(l - 1);
    }
} cur, cur3;
vector <int> adj[MAXN];
int n, m, q;
pair <ll, ll> dd[MAXN];
array <ll, 5> queries[MAXN];
ll ans[MAXN];
ll low[MAXN], high[MAXN];
int dep[MAXN], dp[18][MAXN];
void calc (int pos, int par) {
    dp[0][pos] = par;
    for (auto j : adj[pos]) {
        if (j != par) {
            dep[j] = 1 + dep[pos];
            calc(j, pos);
        }
    }
}
int jump (int a, int b) {
    for (int i = 17; i >= 0; i--) if (b & (1 << i)) a = dp[i][a];
    return a;
}
int lca (int a, int b) {
    if (dep[a] > dep[b]) swap(a, b);
    b = jump(b, dep[b] - dep[a]);
    if (a == b) return a;
    for (int i = 17; i >= 0; i--) {
        int x = dp[i][a], y = dp[i][b];
        if (x && y && x != y) {
            a = x, b = y;
        }
    }
    return dp[0][a];
}
pair <int, int> edges[MAXN];
ll cur2[MAXN], cur4[MAXN], init[MAXN], finn[MAXN];
vector <pair <ll, ll>> updates[MAXN];
vector <array <ll, 4>> updates2[MAXN];
void dfs (int pos, int par) {
    for (auto j : updates[pos]) {
        cur.update(j.first, j.second);
        cur3.update(j.first, 1);
    }
    for (auto j : updates2[pos]) {
        ll z = cur.get(j[1]);
        ll z2 = cur3.get(j[1]);
        if (j[2]) {
            cur2[j[0]] += z; cur4[j[0]] += z2;
        } else {
            cur2[j[0]] -= z; cur4[j[0]] -= z2;
        }
    }
    for (auto j : adj[pos]) {
        if (j != par) {
            dfs(j, pos);
        }
    }
    for (auto j : updates[pos]) {
        cur.update(j.first, -j.second);
        cur3.update(j.first, -1);
    }
}
int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
        edges[i] = {x, y};
    }
    calc(1, 0);
    for (int i = 1; i < 18; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
    for (int i = 1; i < n; i++) {
        if (dep[edges[i].first] < dep[edges[i].second]) {
            swap(edges[i].first, edges[i].second);
        }
    }
    for (int i = 1; i <= m; i++) {
        ll x, y; cin >> x >> y;
        dd[i] = {x, y};
    }
    sort(dd + 1, dd + m + 1, [&] (pair <int, int> x, pair <int, int> y) {
        return x.second < y.second;
    });
    for (int i = 1; i <= m; i++) {
        updates[edges[dd[i].first].first].push_back({i, dd[i].second});
    }
    for (int i = 1; i <= q; i++) {
        ll w, x, y, z; cin >> w >> x >> y >> z;
        queries[i] = {w, x, lca(w, x), z, y};
    }
    for (int i = 1; i <= q; i++) {
        low[i] = 1, high[i] = m, ans[i] = 0;
    }
    {
        cur.init(); cur3.init();
        for (int i = 1; i <= n; i++) {
            updates2[i].clear();
        }
        for (int i = 1; i <= q; i++) {
            cur2[i] = 0; cur4[i] = 0;
            updates2[queries[i][2]].push_back({i, m, 0});
            updates2[queries[i][2]].push_back({i, m, 0});
            updates2[queries[i][0]].push_back({i, m, 1});
            updates2[queries[i][1]].push_back({i, m, 1});
        }
        dfs(1, -1);
        for (int i = 1; i <= q; i++) {
            init[i] = cur4[i];
        }
    }
    for (int iter = 1; iter <= 18; iter++) {
        cur.init(); cur3.init();
        for (int i = 1; i <= n; i++) {
            updates2[i].clear();
        }
        for (int i = 1; i <= q; i++) {
            if (low[i] > high[i]) continue;
            cur2[i] = 0; cur4[i] = 0;
            ll mid2 = (low[i] + high[i]) / 2;
            updates2[queries[i][2]].push_back({i, mid2, 0});
            updates2[queries[i][2]].push_back({i, mid2, 0});
            updates2[queries[i][0]].push_back({i, mid2, 1});
            updates2[queries[i][1]].push_back({i, mid2, 1});
        }
        dfs(1, -1);
        for (int i = 1; i <= q; i++) {
            if (low[i] > high[i]) continue;
            ll mid2 = (low[i] + high[i]) / 2;
            if (cur2[i] <= queries[i][3]) {
                low[i] = mid2 + 1; ans[i] = mid2; finn[i] = cur4[i];
            } else {
                high[i] = mid2 - 1;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        //cout << i << ": " << init[i] << " " << finn[i] << '\n';
        if (init[i] - finn[i] <= queries[i][4]) {
            cout << queries[i][4] - init[i] + finn[i] << '\n';
        } else {
            cout << "-1\n";
        }
    }
}

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