Submission #1105756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105756		Perl32	Two Currencies (JOI23_currencies)	C++14	100 / 100	1796 ms	31292 KiB

currencies

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

struct Q {
    int l, r, x;
    ll y;
    int i;
};

const int K = 3000;
const int maxN = 100'100;
bool used[maxN];

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    vector<pair<int, int>> srt;
    vector<vector<pair<int, int>>> tmp(n - 1);
    for (int i = 0; i < m; ++i) {
        int p, x;
        cin >> p >> x;
        tmp[p - 1].push_back({x, i});
        srt.push_back({x, i});
    }
    sort(srt.begin(), srt.end());
    vector<vector<int>> ex(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        for (auto x : tmp[i]) {
            ex[i].push_back(lower_bound(srt.begin(), srt.end(), x) - srt.begin());
        }
    }
    vector<int> tin(n), ord;
    auto Dfs = [&](auto&& self, int u, int p) -> void {
        tin[u] = (int) ord.size();
        for (auto [to, i] : g[u]) {
            if (to == p) continue;
            for (auto id : ex[i]) ord.push_back(id);
            self(self, to, u);
            for (auto id : ex[i]) ord.push_back(id);
        }
    };
    Dfs(Dfs, 0, -1);
    vector<Q> qry(q);
    for (int i = 0; i < q; ++i) {
        int u, v, x;
        ll y;
        cin >> u >> v >> x >> y;
        u = tin[u - 1], v = tin[v - 1];
        if (u > v) swap(u, v);
        qry[i] = {u, v, x, y, i};
    }
    sort(qry.begin(), qry.end(), [&](auto i, auto j) {
        if (i.l / K != j.l / K) return i.l < j.l;
        return i.r < j.r;
    });
    int sz = (srt.size() + K - 1) / K;
    assert(sz);
    memset(used, 0, sizeof used);
    vector<vector<ll>> bl(sz, vector<ll>(K, 0ll));
    vector<ll> sm(sz, 0ll);
    vector<int> cnt(sz, 0);
    ll s = 0ll;
    int c = 0;
    auto chk = [&](int i) {
        i = ord[i];
        int ii = i / K, iii = i % K;
        if (!used[i]) {
            sm[ii] += srt[i].first;
            bl[ii][iii] += srt[i].first;
            s += srt[i].first;
            cnt[ii]++;
            c++;
        } else {
            sm[ii] -= srt[i].first;
            bl[ii][iii] -= srt[i].first;
            s -= srt[i].first;
            cnt[ii]--;
            c--;
        }
        used[i] ^= 1;
    };
    vector<int> ans(q);
    int cl = 0, cr = 0;
    for (auto [l, r, x, y, id] : qry) {
        while (cl > l) chk(--cl);
        while (cl < l) chk(cl++);
        while (cr > r) chk(--cr);
        while (cr < r) chk(cr++);
        ll cur = s;
        for (int i = sz - 1; i > -1; --i) {
            if (cur - sm[i] <= y) {
                for (int j = K - 1; j > -1 && cur > y; --j) {
                    if (bl[i][j]) {
                        x--;
                        cur -= bl[i][j];
                    }
                }
                break;
            } else {
                x -= cnt[i];
                cur -= sm[i];
            }
        }
        ans[id] = max(-1, x);
    }
    for (auto x : ans) cout << x << '\n';
}

/*

 */

Compilation message (stderr)

currencies.cpp: In lambda function:
currencies.cpp:55:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         for (auto [to, i] : g[u]) {
      |                   ^
currencies.cpp: In function 'int main(int32_t, char**)':
currencies.cpp:104:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |     for (auto [l, r, x, y, id] : qry) {
      |               ^

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