Submission #992726

#	Time	Username	Problem	Language	Result	Execution time	Memory
992726		KietJ	Two Currencies (JOI23_currencies)	C++17	100 / 100	1321 ms	102620 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
 
typedef long long ll;
typedef pair <int, int> ii;
 
const int N = 3e5 + 5;
const int mod = 998244353; 
 
struct Bit {
    int n; vector <ll> bit;
    Bit (int _n): n(_n), bit(_n + 2, 0) {};
 
    void up(int x, int val) {
        for(; x <= n; x += (x & -x)) bit[x] += val;
    }
 
    ll get(int x) {
        ll ans = 0;
        for(; x; x -= (x & -x)) ans += bit[x];
        return ans;
    }
 
    void up_range(int l, int r, int val) {
        up(l, val), up(r + 1, -val);
    }
} B1(N), B2(N);
 
int n, m, q, timer = 0, p[20][N], in[N], ou[N], id[N], ans[N];
vector <ii> ed[N], save;
 
void dfs(int u, int par) {
    p[0][u] = par;
    for(int i = 1; i < 20; i++) 
        p[i][u] = p[i - 1][p[i - 1][u]];
    in[u] = ++timer;
 
    for(auto v: ed[u]) {
        if (v.f == par) continue;
        id[v.s] = v.f;
        dfs(v.f, u);
    }
 
    ou[u] = timer;
}
 
bool is(int a, int b) {
    return in[a] <= in[b] && ou[b] <= ou[a];
}
 
int lca(int a, int b) {
    if (is(a, b)) return a;
    if (is(b, a)) return b;
 
    for(int i = 19; i >= 0; i--) {
        if (!is(p[i][a], b))
            a = p[i][a];
    }
 
    return p[0][a];
}
 
ll sum(int a, int b, Bit& B) {
    int c = lca(a, b);
    return B.get(in[a]) + B.get(in[b]) - 2 * B.get(in[c]);
}
 
void para(int l, int r, vector <vector <ll>>& queries) {
    if (l > r || !sz(queries)) return;
 
    int m = (l + r) / 2;
 
    for(int i = l; i <= m; i++) {
        int c = save[i].f, p = save[i].s;
        B1.up_range(in[p], ou[p], c);
        B2.up_range(in[p], ou[p], 1);
    }
 
    vector <vector <ll>> win, lose;
 
    for(auto x: queries) {
        if (sum(x[0], x[1], B1) <= x[3]) {
            ans[x[4]] -= sum(x[0], x[1], B2);
            win.push_back(x);
            win.back()[3] -= sum(x[0], x[1], B1);
        } else {
            lose.push_back(x);
        }
    }
 
    for(int i = l; i <= m; i++) {
        int c = save[i].f, p = save[i].s;
        B1.up_range(in[p], ou[p], -c);
        B2.up_range(in[p], ou[p], -1);
    }
 
    if (l != r) 
        para(l, m, lose); vector <vector <ll>> ().swap(lose);
    para(m + 1, r, win); vector <vector <ll>> ().swap(win);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m >> q;
 
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        ed[u].push_back({v, i});
        ed[v].push_back({u, i});
    }
 
    dfs(1, 1);
 
    for(int i = 1; i <= m; i++) {
        int p, c; cin >> p >> c;
        p = id[p]; B2.up_range(in[p], ou[p], 1);
        save.push_back({c, p});
    }
 
    sort(all(save));
 
    vector <vector <ll>> queries;
    for(int i = 0; i < q; i++) {
        ll s, t, x, y; cin >> s >> t >> x >> y;
        ans[i] += sum(s, t, B2);
        queries.push_back({s, t, x, y, i});
    }
    
    for(auto x: save) 
        B2.up_range(in[x.s], ou[x.s], -1);
    
    para(0, sz(save) - 1, queries);
 
    for(int i = 0; i < q; i++) 
        cout << max(-1ll, queries[i][2] - ans[i]) << "\n";
 
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void para(int, int, std::vector<std::vector<long long int> >&)':
currencies.cpp:102:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  102 |     if (l != r)
      |     ^~
currencies.cpp:103:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  103 |         para(l, m, lose); vector <vector <ll>> ().swap(lose);
      |                           ^~~~~~

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