Submission #749209

#	Time	Username	Problem	Language	Result	Execution time	Memory
749209		Lucpp	Two Currencies (JOI23_currencies)	C++17	100 / 100	2834 ms	197644 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
constexpr int LOG = 18;

struct PSeg{
    int cap;
    vector<pl> seg;
    vector<int> L, R;

    pl combine(pl a, pl b){
        return {a.first + b.first, a.second + b.second};
    }

    PSeg(vector<pl> v){
        int n = (int)v.size();
        for(cap = 1; cap < n; cap*=2);
        seg.resize(2*cap);
        L.assign(2*cap, -1);
        R.assign(2*cap, -1);
        for(int i = 0; i < n; i++) seg[i+cap] = v[i];
        for(int i = cap-1; i >= 1; i--){
            L[i] = 2*i; R[i] = 2*i+1;
            seg[i] = combine(seg[L[i]], seg[R[i]]);
        }
    }

    int upd(int p, pl val, int i, int l, int r){
        int mid = (l+r)/2;
        int my = (int)seg.size();
        L.push_back(L[i]);
        R.push_back(R[i]);
        seg.push_back(val);
        if(l == r) return my;
        if(p <= mid){
            int nl = upd(p, val, L[i], l, mid);
            L[my] = nl;
        } else {
            int nr = upd(p, val, R[i], mid+1, r);
            R[my] = nr;
        }
        seg[my] = combine(seg[L[my]], seg[R[my]]);
        return my;
    }
    int upd(int p, pl val, int i){return upd(p+1, val, i, 1, cap);}

    pl qry(int l, int r, int a, int b, int i){
        if(l <= a && b <= r) return seg[i];
        if(b < l || r < a) return {0, 0};
        int m = (a+b)/2;
        return combine(qry(l, r, a, m, L[i]), qry(l, r, m+1, b, R[i]));
    }
    pl qry(int l, int r, int i){return qry(l+1, r+1, 1, cap, i);}
};

vector<vector<int>> cid;
vector<vector<pi>> g;
vector<vector<int>> jump;
vector<int> depth;
int timer = 0;
vector<int> ct1, ct2, tin;

void dfs(int u, int par){
    tin[u] = timer;
    jump[0][u] = par;
    for(auto [v, i] : g[u]){
        if(v == par) continue;
        depth[v] = depth[u]+1;
        for(int id : cid[i]){
            ct1[id] = timer++;
        }
        dfs(v, u);
        for(int id : cid[i]){
            ct2[id] = timer++;
        }
    }
}

int lift(int u, int x){
    for(int i = 0; i < LOG; i++){
        if(x & (1<<i)) u = jump[i][u];
    }
    return u;
}

int lca(int a, int b){
    if(depth[a] < depth[b]) swap(a, b);
    a = lift(a, depth[a]-depth[b]);
    if(a == b) return a;
    for(int i = LOG-1; i >= 0; i--){
        if(jump[i][a] != jump[i][b]){
            a = jump[i][a];
            b = jump[i][b];
        }
    }
    return jump[0][a];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    g.resize(N);
    cid.resize(N-1);
    jump.assign(LOG, vector<int>(N));
    depth.resize(N);
    ct1.resize(M);
    ct2.resize(M);
    tin.resize(N);
    vector<pair<ll, int>> checks(M);
    for(int i = 0; i < N-1; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }
    for(int i = 0; i < M; i++){
        int p; ll cost;
        cin >> p >> cost;
        p--;
        cid[p].push_back(i);
        checks[i] = {cost, i};
    }
    dfs(0, 0);
    for(int k = 1; k < LOG; k++){
        for(int i = 0; i < N; i++){
            jump[k][i] = jump[k-1][jump[k-1][i]];
        }
    }
    sort(checks.rbegin(), checks.rend());
    vector<pl> start_val(2*M);
    for(auto [cost, p] : checks){
        start_val[ct1[p]] = {0, cost};
        start_val[ct2[p]] = {0, -cost};
    }
    PSeg seg(start_val);
    vector<int> nodes{1};
    for(auto [cost, p] : checks){
        int cur = nodes.back();
        cur = seg.upd(ct1[p], {1, 0}, cur);
        cur = seg.upd(ct2[p], {-1, 0}, cur);
        nodes.push_back(cur);
    }
    for(int q = 0; q < Q; q++){
        int s, t;
        ll x, y;
        cin >> s >> t >> x >> y;
        s--, t--;
        int mylca = lca(s, t);
        // cerr << s << " " << t << " " << mylca << "\n";
        auto calc = [&](int node){
            pl val = {0, 0};
            val = seg.combine(val, seg.qry(tin[mylca], tin[s]-1, node));
            val = seg.combine(val, seg.qry(tin[mylca], tin[t]-1, node));
            // cerr << val.first << " " << val.second << "\n";
            return val;
        };
        int lo = 0, hi = M;
        for(int m=(lo+hi)/2; lo<hi; m=(lo+hi)/2){
            pl val = calc(nodes[m]);
            // cerr << val.first << " " << val.second << "\n";
            if(val.second > y) lo = m+1;
            else hi = m;
        }
        pl val = calc(nodes[lo]);
        assert(val.second <= y);
        if(val.first > x) cout << "-1\n";
        else cout << x - val.first << "\n";
    }
}

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