Submission #878887

#	Time	Username	Problem	Language	Result	Execution time	Memory
878887		pemguimn	Two Currencies (JOI23_currencies)	C++14	100 / 100	3034 ms	65444 KiB

currencies

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define gcd __gcd
#define endl "\n"
#define task "hihi"
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;  
int n, m, q, par[18][N], h[N], c[N], num[N], tail[N], lo[N], hi[N], bit1[N], bit2[N], ans[N], timedfs = 0;
vector<pii> edges(N + 5);
vector<int> adj[N];
vector<int> pos[N];
array<int, 4> a[N];
pii b[N];
void dfs(int i, int pre){
    num[i] = ++timedfs;
    for(int x : adj[i]){
        if(x == pre) continue;
        h[x] = h[i] + 1;
        par[0][x] = i;
        for(int j = 1; j < 18; j++) par[j][x] = par[j - 1][par[j - 1][x]];
        dfs(x, i);
    }
    tail[i] = timedfs;
}
void upd(int bit[], int x, int val){
    for(; x <= n; x += x & -x){
        bit[x] += val;
    }
}
void upd(int bit[], int l, int r, int val){
    upd(bit, l, val);
    upd(bit, r + 1, -val);
}
int query(int bit[], int x){
    int res = 0;
    for(; x; x -= x & -x){
        res += bit[x];
    }
    return res;
}
int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int dist = h[x] - h[y];
    for(int i = 0; i < 18; i++){
        if(dist & (1 << i)) x = par[i][x];
    }
    if(x == y) return x;
    for(int i = 17; i >= 0; i--){
        if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
    }
    return par[0][x];
}
int get(int bit[], int x, int y){
    if(h[x] > h[y]) swap(x, y);
    int u = lca(x, y);
    if(x == u){
        return query(bit, num[y]) - query(bit, num[x]);
    } else{
        return query(bit, num[x]) + query(bit, num[y]) - 2 * query(bit, num[u]);
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1, x, y; i < n; i++){
        cin >> x >> y;
        adj[x].pb(y), adj[y].pb(x);
        edges[i] = {x, y};
    }
    dfs(1, 1);
    for(int i = 1; i <= n; i++){
        if(h[edges[i].first] > h[edges[i].second]) swap(edges[i].first, edges[i].second);
    }
    for(int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        b[i] = {edges[x].second, y};
    }
    sort(b + 1, b + m + 1, [](pii x, pii y){return x.second < y.second;});

    for(int i = 1; i <= q; i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
        // start end gold silver
        lo[i] = 1, hi[i] = m, ans[i] = -1;
    }
    for(int i = 1; i <= m; i++){
        upd(bit2, num[b[i].first], tail[b[i].first], 1);
    }
    for(int i = 1; i <= q; i++){
        int cur2 = get(bit2, a[i][0], a[i][1]);
        if(cur2 <= a[i][2]) ans[i] = a[i][2] - cur2;
    }
    for(int i = 1; i <= m; i++){
        upd(bit2, num[b[i].first], tail[b[i].first], -1);
    }
    // cout << endl;
    // for(int i = 1; i <= m; i++){
    //     cout << b[i].first << " " << b[i].second << endl;
    // }
    // cout << endl;

    for(int phase = 0; phase < 18; phase++){
        for(int j = 1; j <= m; j++){
            pos[j].clear();       
        }
        for(int j = 1; j <= q; j++){
            if(lo[j] > hi[j]) continue;
            int mid = (lo[j] + hi[j]) / 2;
            pos[mid].pb(j);
        }
        for(int i = 1; i <= m; i++){
            upd(bit2, num[b[i].first], tail[b[i].first], 1);
        }
        for(int i = 1; i <= m; i++){
            upd(bit1, num[b[i].first], tail[b[i].first], b[i].second);
            upd(bit2, num[b[i].first], tail[b[i].first], -1);
            for(int x : pos[i]){
                int cur = get(bit1, a[x][0], a[x][1]), cur2 = get(bit2, a[x][0], a[x][1]);
                // cout << i << " " << x << " " << a[x][0] << " " << a[x][1] << " " << cur << endl;
                if(cur <= a[x][3]){
                    lo[x] = i + 1;
                    if(cur2 <= a[x][2]) ans[x] = a[x][2] - cur2;
                } else{
                    hi[x] = i - 1;
                }
            }
        }
        for(int i = 0; i <= n; i++){
            bit1[i] = bit2[i] = 0;
        }
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
    return 0;
}

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