Submission #986479

#	Time	Username	Problem	Language	Result	Execution time	Memory
986479		876pol	Two Currencies (JOI23_currencies)	C++17	0 / 100	5030 ms	14748 KiB

currencies

#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()

#define MOD 1000000007
// #define MOD 998244353

#define FASTIO
#define PRECISION
// #define FILE "file"

#define SINGLE
// #define MULTIPLE
// #define GOOGLE

void st1() {
    ll n, m, q;
    cin >> n >> m >> q;
    vvpll graph(n + 1);
    CFOR(i, 1, n - 1) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
    }
    vvll check(n);
    FOR(i, 0, m) {
        ll p, c;
        cin >> p >> c;
        check[p].push_back(c);
    }
    FOR(i, 0, q) {
        ll s, t, x, y;
        cin >> s >> t >> x >> y;
        vll cs;
        function<bool(ll, ll)> dfs = [&](ll curr, ll prev) -> bool {
            if (curr == t) return true;
            TRAV(e, graph[curr]) {
                if (e.first == prev) continue;
                FOR(i, 0, check[e.second].size()) {
                    cs.push_back(check[e.second][i]);
                }
                if (dfs(e.first, curr)) return true;
                FOR(i, 0, check[e.second].size()) {
                    cs.pop_back();
                }
            }
            return false;
        };
        dfs(s, -1);
        sort(all(cs));
        reverse(all(cs));
        while (cs.size() && cs.back() <= y) {
            y -= cs.back();
            cs.pop_back();
        }
        if (x < cs.size()) {
            cout << "-1\n";
        } else {
            cout << x - cs.size() << "\n";
        }
    }
}

void st2() {
    ll n, m, q;
    cin >> n >> m >> q;
    vvpll graph(n + 1);
    CFOR(i, 1, n - 1) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
    }
    ll c;
    vvll check(n);
    FOR(i, 0, m) {
        ll p;
        cin >> p >> c;
        check[p].push_back(c);
    }
    vll nc(n + 1), level(n + 1);
    ll L = 20;
    vvll up(L, vll(n + 1));
    function<void(ll, ll)> dfs = [&](ll curr, ll prev) {
        up[0][curr] = prev;
        FOR(i, 1, 20) up[i][curr] = up[i - 1][up[i - 1][curr]];
        level[curr] = level[prev] + 1;
        TRAV(e, graph[curr]) {
            if (e.first == prev) continue;
            nc[e.first] = nc[curr] + check[e.second].size();
            dfs(e.first, curr);
        }
    };
    dfs(1, 0);
    function<ll(ll, ll)> lca = [&](ll x, ll y) -> ll {
        if (level[x] < level[y]) swap(x, y);
        if (level[x] > level[y]) {
            RFOR(i, 20, 0) {
                if (level[up[i][x]] > level[y]) {
                    x = up[i][x];
                }
            }
            x = up[0][x];
        }
        RFOR(i, 20, 0) {
            if (up[i][x] != up[i][y]) {
                x = up[i][x];
                y = up[i][y];
            }
        }
        if (x != y) {
            x = up[0][x];
            y = up[0][y];
        }
        assert(x == y);
        return x;
    };
    FOR(i, 0, q) {
        ll s, t, x, y;
        cin >> s >> t >> x >> y;
        ll cnt = nc[s] + nc[t] - 2 * nc[lca(s, t)];
        while (cnt && c <= y) {
            y -= c;
            cnt--;
        }
        if (x < cnt) {
            cout << "-1\n";
        } else {
            cout << x - cnt << "\n";
        }
    }
}

struct query {
    ll s, t, x, y, i;
};

STRUCT_DBG(query, false, &query::s, &query::t, &query::x, &query::y);

void st3() {
    ll n, m, q;
    cin >> n >> m >> q;
    vvpll graph(n + 1);
    CFOR(i, 1, n - 1) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
    }
    vpll a(m);
    vll cc;
    FOR(i, 0, m) {
        cin >> a[i].first >> a[i].second;
        cc.push_back(a[i].second);
    }
    sort(all(a));
    sort(all(cc));
    cc.erase(unique(all(cc)), cc.end());
    auto f = [&](ll x) { return lower_bound(all(cc), x) - cc.begin(); };
    vll sm(2 * cc.size()), ct(2 * cc.size());
#define lc(v) (v + 1)
#define rc(v) (v + 2 * (tm - tl + 1))
    function<void(ll, ll, ll, ll, ll)> update = [&](ll v, ll tl, ll tr, ll ind,
                                                    ll x) {
        if (tl == tr && tl == ind) {
            sm[v] += x * cc[ind];
            ct[v] += x;
        } else {
            ll tm = (tl + tr) / 2;
            if (ind <= tm) {
                update(lc(v), tl, tm, ind, x);
            } else {
                update(rc(v), tm + 1, tr, ind, x);
            }
            sm[v] = sm[lc(v)] + sm[rc(v)];
            ct[v] = ct[lc(v)] + ct[rc(v)];
        }
    };
    function<ll(ll, ll, ll, ll)> walk = [&](ll v, ll tl, ll tr, ll y) -> ll {
        if (y <= 0) return 0;
        if (tl == tr) {
            return min(ct[v], y / cc[tl]);
        } else {
            ll tm = (tl + tr) / 2;
            if (sm[lc(v)] <= y) {
                return ct[lc(v)] + walk(rc(v), tm + 1, tr, y - sm[lc(v)]);
            } else {
                return walk(lc(v), tl, tm, y);
            }
        }
    };
    ll SZ = 300;
    vll ans(q);
    vec<vec<query>> qus((m + SZ - 1) / SZ);
    FOR(i, 0, q) {
        query qu;
        cin >> qu.s >> qu.t >> qu.x >> qu.y;
        qu.i = i;
        if (qu.s > qu.t) swap(qu.s, qu.t);
        qu.s = lower_bound(all(a), pll{qu.s, LLONG_MIN}) - a.begin();
        qu.t = lower_bound(all(a), pll{qu.t, LLONG_MIN}) - a.begin();
        if (qu.s == a.size()) {
            ans[qu.i] = qu.x;
            continue;
        }
        qus[qu.s / SZ].push_back(qu);
    }
    FOR(i, 0, (m + SZ - 1) / SZ) {
        fill(all(sm), 0ll);
        fill(all(ct), 0ll);
        sort(all(qus[i]),
             [&](const query &o1, const query &o2) { return o1.t < o2.t; });
        ll l = (i * SZ);
        ll r = (i * SZ);
        TRAV(e, qus[i]) {
            while (r < e.t) {
                update(0, 0, cc.size() - 1, f(a[r].second), 1);
                r++;
            }
            while (l < e.s) {
                update(0, 0, cc.size() - 1, f(a[l].second), -1);
                l++;
            }
            while (e.s < l) {
                l--;
                update(0, 0, cc.size() - 1, f(a[l].second), 1);
            }
            ans[e.i] =
                max(-1ll, e.x - (ct[0] - walk(0, 0, cc.size() - 1, e.y)));
        }
    }
    FOR(i, 0, q) {
        cout << ans[i] << "\n";
    }
}

void solve() {
    st3();
}

int main() {
#ifdef FASTIO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#endif
#ifdef PRECISION
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
#endif
#ifdef FILE
    freopen((FILE + string(".in")).c_str(), "r", stdin);
    freopen((FILE + string(".out")).c_str(), "w", stdout);
#endif
#ifdef SINGLE
    solve();
#endif
#ifdef MULTIPLE
    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        solve();
    }
#endif
#ifdef GOOGLE
    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
#endif
}

Compilation message (stderr)

currencies.cpp: In function 'void st1()':
currencies.cpp:88:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         if (x < cs.size()) {
      |             ~~^~~~~~~~~~~
currencies.cpp: In function 'void st3()':
currencies.cpp:234:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  234 |         if (qu.s == a.size()) {
      |             ~~~~~^~~~~~~~~~~

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