Submission #939890

#	Time	Username	Problem	Language	Result	Execution time	Memory
939890		nextgenxing	Two Currencies (JOI23_currencies)	C++14	100 / 100	4564 ms	107964 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define F0Rd(i, x) FORd(i, 0, x)
const int MAX_N = 1e5+5;
const ll INF = 1e18;

int n, m, q, t, cnt;
int dep[MAX_N], anc[MAX_N][20], rt[MAX_N], ch[50*MAX_N][2];
ll sm[50*MAX_N], num[50*MAX_N];
vector<ll> nums[MAX_N];
vector<pii> adj[MAX_N];

int upd(int x, ll v, ll l = 0, ll r = 1e9){
    ll x2 = ++cnt, m = (l+r)/2ll;
    if(l == r){
        sm[x2] = sm[x]+v;
        num[x2] = num[x]+1;
        return x2;
    }
    if(v <= m){
        ch[x2][0] = upd(ch[x][0], v, l, m);
        ch[x2][1] = ch[x][1];
    } else{
        ch[x2][0] = ch[x][0];
        ch[x2][1] = upd(ch[x][1], v, m+1ll, r);
    }
    sm[x2] = sm[ch[x2][0]]+sm[ch[x2][1]];
    num[x2] = num[ch[x2][0]]+num[ch[x2][1]];
    return x2;
}

ll qry1(int x, ll ql, ll qr, ll l = 0, ll r = 1e9){
    if(!x || ql > r || qr < l) return 0;
    if(ql <= l && qr >= r) return sm[x];
    ll m = (l+r)/2ll;
    return qry1(ch[x][0], ql, qr, l, m)+qry1(ch[x][1], ql, qr, m+1, r);
}

ll qry2(int x, ll ql, ll qr, ll l = 0, ll r = 1e9){
    if(!x || ql > r || qr < l) return 0;
    if(ql <= l && qr >= r) return num[x];
    ll m = (l+r)/2ll;
    return qry2(ch[x][0], ql, qr, l, m)+qry2(ch[x][1], ql, qr, m+1, r);
}

void dfs(int curr, int par){
    for(auto x : adj[curr]){
        if(x.ff == par) continue;
        dep[x.ff] = dep[curr]+1;
        anc[x.ff][0] = curr;
        rt[x.ff] = rt[curr];
        for(auto y : nums[x.ss])
            rt[x.ff] = upd(rt[x.ff], y);
        dfs(x.ff, curr);
    }
}

int lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    F0Rd(i, 20) if(dep[a]+(1 << i) <= dep[b])
        b = anc[b][i];
    if(a == b) return a;
    F0Rd(i, 20) if(anc[a][i] != anc[b][i])
        a = anc[a][i], b = anc[b][i];
    return anc[a][0];
}

pair<pii, ll> solve(int a, int b, ll x){ // number of things > x, number of things = x, sum of things < x
    int c = lca(a, b);
    pii y = {qry2(rt[a], x+1, 1e9)+qry2(rt[b], x+1, 1e9)-2ll*qry2(rt[c], x+1, 1e9), qry2(rt[a], x, x)+qry2(rt[b], x, x)-2ll*qry2(rt[c], x, x)};
    pair<pii, ll> ans = {y, qry1(rt[a], 0, x-1ll)+qry1(rt[b], 0, x-1ll)-2ll*qry1(rt[c], 0, x-1ll)};
    return ans;
}

int main(int argc, const char * argv[]){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> m >> q;
    F0R(i, n-1){
        int a, b; cin >> a >> b; a--, b--;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    F0R(i, m){
        int a, b; cin >> a >> b; a--;
        nums[a].push_back(b);
    }
    dfs(0, -1);
    FOR(x, 1, 20) F0R(i, n)
        anc[i][x] = anc[anc[i][x-1]][x-1];
    F0R(i, q){
        ll s, t, x, y; cin >> s >> t >> x >> y; s--, t--;
        ll l = 0, r = min(y+1ll, (ll) 1e9);
        while(l+1 < r){
            ll mid = (l+r)/2ll;
            if(solve(s, t, mid).ss <= y) l = mid;
            else r = mid;
        }
        pair<pll, ll> z = solve(s, t, l);
        pll ans = {z.ff.ff, z.ss};
        if(z.ff.ss*l+z.ss <= y) ans.ss += z.ff.ss;
        else ans.ss += l*((y-z.ss)/l), ans.ff += z.ff.ss-(y-z.ss)/l;
        if(ans.ff > x) cout << "-1\n";
        else cout << x-ans.ff << '\n';
    }
    return 0;
}

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