Submission #955628

#	Time	Username	Problem	Language	Result	Execution time	Memory
955628		vjudge1	Two Currencies (JOI23_currencies)	C++17	100 / 100	2013 ms	129108 KiB

currencies

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// ^ desperate
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int const N = 1e5+10;
int const M = 1e7;

struct S{
    int l, r;
    ll v; int c;
} seg[M];
int rt[N];
int segcnt = 0;
int nodeseg1(ll v, int c){
    seg[segcnt].v = v;
    seg[segcnt].c = c;
    return segcnt++;
};
int nodeseg2(int l, int r){
    seg[segcnt].l = l; seg[segcnt].r = r;
    seg[segcnt].v = seg[l].v + seg[r].v;
    seg[segcnt].c = seg[l].c + seg[r].c;
    return segcnt++;
}
int buildseg(int l, int r){
    if (l==r) return nodeseg1(0,0);
    int m = (l+r)/2;
    return nodeseg2(buildseg(l,m),buildseg(m+1,r));
}
int updseg(int u, int pos, ll v, int l, int r){
    if (l>pos||r<pos) return u;
    if (l==r) return nodeseg1(seg[u].v + v, seg[u].c+(v>0?1:-1));
    int m = (l+r)/2;
    int _l = updseg(seg[u].l, pos, v, l, m),
        _r = updseg(seg[u].r, pos, v, m+1, r);
    return nodeseg2(_l, _r);
}
pair<ll,ll> query(int u, int i, int j, int l, int r){
    if (i>j) return make_pair(0LL,0LL);
    if (i <= l && r <= j) return make_pair(seg[u].v, seg[u].c);
    int m = (l+r)/2;
    pair<ll,ll> ql = query(seg[u].l, i, min(m,j), l, m),
        qr = query(seg[u].r, max(m+1,i), j, m+1, r);
    return make_pair(ql.first+qr.first, ql.second+qr.second);
}

struct Edge{
    int u, v;
    Edge() {}
    Edge(int u, int v) : u(u), v(v) {}
    int get(int x) { return u^v^x; }
};
vector<Edge> E;
vector<int> G[N];

int tin[N], tout[N], B[N], tt, dd;
int ent[N], tt2;
pair<int,int> lcas[6*N];
void dfs(int u){
    ent[u] = ++tt2;
    lcas[tt2] = make_pair(dd, u);
    for (int i: G[u]){
        int v = E[i].get(u);
        if (ent[v]) continue;
        B[v] = i;
        tin[i] = ++tt;
        ++dd;
        dfs(v);
        --dd;
        tout[i] = ++tt;
        lcas[++tt2] = make_pair(dd, u);
    }
}
void build(){
    for (int i = 0; i <= tt2; ++i) lcas[i+tt2+1] = lcas[i];
    for (int i=tt2; i; --i) lcas[i] = min(lcas[i<<1], lcas[i<<1|1]);
}
int lca(int u, int v){
    pair<int,int> pp = make_pair(1e8, 0);
    int aa = ent[u], bb = ent[v];
    if (aa > bb) swap(aa, bb);
    for (aa += tt2+1, bb += tt2+2; aa < bb; aa >>= 1, bb >>= 1){
        if (aa&1) pp = min(pp, lcas[aa++]);
        if (bb&1) pp = min(pp, lcas[--bb]);
    }
    return pp.second;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    E.emplace_back(0, 1);
    for (int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        E.emplace_back(u, v);
    }
    vector<pair<ll,int>> upd;
    for (int i = 1; i <= m; ++i){
        int p; ll c; cin >> p >> c;
        upd.emplace_back(c,p);
    }
    sort(upd.begin(), upd.end());
    for (int i = 0; i < (int)E.size(); ++i){
        G[E[i].u].push_back(i);
        G[E[i].v].push_back(i);
    }
    dfs(0);
    build();
    int root = buildseg(1, tt);
    for (int i = 0; i < (int)upd.size(); ++i){
        auto x = upd[i];
        int idx; ll w;
        tie(w, idx) = x;
        root = rt[i] = updseg(root, tin[idx], w, 1, tt);
        root = rt[i] = updseg(root, tout[idx], -w, 1, tt);
    }

    for (int i = 0; i < q; ++i){
        int u, v;
        ll x, y;
        cin >> u >> v >> x >> y;
        int p = lca(u,v);
        int lvert = 0, rvert = upd.size()-1;
        ll xx=0, yy=0;
        while (lvert <= rvert){
            int mvert = (lvert+rvert+1)/2;
            pair<ll,ll> uq = query(rt[mvert], tin[B[1]], tin[B[u]], 1, tt);
            pair<ll,ll> vq = query(rt[mvert], tin[B[1]], tin[B[v]], 1, tt);
            pair<ll,ll> pq = query(rt[mvert], tin[B[1]], tin[B[p]], 1, tt);
            yy = uq.first+vq.first-pq.first*2;
            ll x2 = uq.second+vq.second-pq.second*2;
            if (yy <= y) xx = x2, lvert=mvert+1;
            else rvert=mvert-1;
        }
        pair<ll,ll> uq = query(root, tin[B[1]], tin[B[u]], 1, tt);
        pair<ll,ll> vq = query(root, tin[B[1]], tin[B[v]], 1, tt);
        pair<ll,ll> pq = query(root, tin[B[1]], tin[B[p]], 1, tt);
        ll xz = uq.second+vq.second-pq.second*2;
        if (x < xz-xx) {
            cout << -1 << '\n';
        }
        else {
            cout << (x-xz+xx) << '\n';
        }
    }
}

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