oj.uz

Submission #868437

# Submission time Handle Problem Language Result Execution time Memory
868437 2023-10-31T13:27:22 Z t6twotwo Two Currencies (JOI23_currencies) C++17
100 / 100
 2964 ms 201388 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class S, S (*f)(S, S), S e>
struct PST {
    struct T {
        T *l, *r; S s;
        T() : s() {l = r = nullptr;}
        T(const S &v) : s(v) {l = r = nullptr;}
        T(T *t) : l(t->l), r(t->r), s(t->s) {}
        T(T *a, T *b) : l(a), r(b), s() {
            if (l) s = f(s, l->s);
            if (r) s = f(s, r->s);
        }
    };
    int n;
    vector<T*> rts;
    PST(int m) : PST(vector<S>(m, e)) {
    }
    PST(const vector<S> &a) : n(a.size()) {
        function<T*(int, int)> bld = [&](int l, int r) {
            if (l + 1 == r) {
                return new T(a[l]);
            }
            int m = (l + r) / 2;
            return new T(bld(l, m), bld(m, r));
        };
        rts.push_back(bld(0, n));
    }
    T* set(T *i, int l, int r, int p, const S &v) {
        if (l + 1 == r) {
            return new T(v);
        }
        int m = (l + r) / 2;
        if (p < m) {
            return new T(set(i->l, l, m, p, v), i->r);
        } else {
            return new T(i->l, set(i->r, m, r, p, v));
        }
    }
    T* upd(T *i, int l, int r, int p, const S &v) {
        if (l + 1 == r) {
            return new T(f(i->s, v));
        }
        int m = (l + r) / 2;
        if (p < m) {
            return new T(upd(i->l, l, m, p, v), i->r);
        } else {
            return new T(i->l, upd(i->r, m, r, p, v));
        }
    }
    S qry(T *i, int l, int r, int L, int R) {
        if (R <= l || r <= L) {
            return e;
        }
        if (L <= l && r <= R) {
            return i->s;
        }
        int m = (l + r) / 2;
        return f(qry(i->l, l, m, L, R), qry(i->r, m, r, L, R));
    }
    int lst() {
        return rts.size() - 1;
    }
    int cpy(int k) {
        rts.push_back(new T(rts[k]));
        return rts.size() - 1;
    }
    void set(int k, int i, const S &v) {
        rts[k] = set(rts[k], 0, n, i, v);
    }
    void upd(int k, int i, const S &v) {
        rts[k] = upd(rts[k], 0, n, i, v);
    }
    S qry(int k, int l, int r) {
        return qry(rts[k], 0, n, l, r);
    }
};
ll F(ll x, ll y) {
    return x + y;
}
template<int SZ, bool VALS_IN_EDGES> struct HLD { 
	int N; vector<int> adj[SZ];
	int par[SZ], root[SZ], depth[SZ], sz[SZ], ti;
	int pos[SZ]; vector<int> rpos; // rpos not used but could be useful
	void ae(int x, int y) { adj[x].push_back(y), adj[y].push_back(x); }
	void dfsSz(int x) { 
		sz[x] = 1; 
		for(auto &y:adj[x]) {
			par[y] = x; depth[y] = depth[x]+1;
			adj[y].erase(find(adj[y].begin(), adj[y].end(),x)); /// remove parent from adj list
			dfsSz(y); sz[x] += sz[y];
			if (sz[y] > sz[adj[x][0]]) swap(y,adj[x][0]);
		}
	}
	void dfsHld(int x) {
		pos[x] = ti++; rpos.push_back(x);
		for(auto &y:adj[x]) {
			root[y] = (y == adj[x][0] ? root[x] : y);
			dfsHld(y); }
	}
	void init(int _N, int R = 0) { N = _N; 
		par[R] = depth[R] = ti = 0; dfsSz(R); 
		root[R] = R; dfsHld(R); 
	}
	int lca(int x, int y) {
		for (; root[x] != root[y]; y = par[root[y]])
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
		return depth[x] < depth[y] ? x : y;
	}
	/// int dist(int x, int y) { // # edges on path
	/// 	return depth[x]+depth[y]-2*depth[lca(x,y)]; }
	// LazySeg<ll,SZ> tree; // segtree for sum
	template <class BinaryOp>
	void processPath(int x, int y, BinaryOp op) {
		for (; root[x] != root[y]; y = par[root[y]]) {
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
			op(pos[root[y]],pos[y]); }
		if (depth[x] > depth[y]) swap(x,y);
		op(pos[x]+VALS_IN_EDGES,pos[y]); 
	}
	// void modifyPath(int x, int y, int v) { 
	// 	processPath(x,y,[this,&v](int l, int r) { 
	// 		tree.upd(l,r,v); }); }
	// ll queryPath(int x, int y) { 
	// 	ll res = 0; processPath(x,y,[this,&res](int l, int r) { 
	// 		res += tree.query(l,r); });
	// 	return res; }
	// void modifySubtree(int x, int v) { 
	// 	tree.upd(pos[x]+VALS_IN_EDGES,pos[x]+sz[x]-1,v); }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<pair<int, int>> edges(N - 1);
    vector<vector<int>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        edges[i] = {x, y};
        adj[x].push_back(i);
        adj[y].push_back(i);
    }
    vector<pair<int, int>> ch(M);
    for (int i = 0; i < M; i++) {
        int p, c;
        cin >> p >> c;
        ch[i] = {c, p - 1};
    }
    sort(ch.begin(), ch.end());
    vector<int> t(N - 1);
    {
        auto dfs = [&](auto dfs, int x, int p) -> void {
            for (int z : adj[x]) {
                auto [u, v] = edges[z];
                int y = x ^ u ^ v;
                if (y != p) {
                    t[z] = y;
                    dfs(dfs, y, x);
                }
            }
        };
        dfs(dfs, 0, -1);
    }
    HLD<1000000, 1> hld;
    for (int i = 0; i < N; i++) {
        for (int &j : adj[i]) {
            auto [x, y] = edges[j];
            j = i ^ x ^ y;
            if (j < i) {
                hld.ae(i, j);
            }
        }
    }
    hld.init(N);
    PST<ll, F, 0> q(N);
    for (int i = 0; i < M; i++) {
        auto [c, p] = ch[i];
        q.upd(q.cpy(q.lst()), hld.pos[t[p]], c);
    }
    auto get = [&](int x, int y, int z) -> ll {
        ll s = 0;
        hld.processPath(x, y, [&](int l, int r) {
            s += q.qry(z, l, r + 1);
        });
        return s;
    };
    vector<int> S(Q), T(Q), X(Q), a(Q);
    vector<ll> Y(Q);
    for (int i = 0; i < Q; i++) {
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        S[i]--, T[i]--;
        int lo = 0, hi = M;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            if (get(S[i], T[i], mi) <= Y[i]) {
                lo = mi;
            } else {
                hi = mi - 1;
            }
        }
        a[i] = lo;
    }
    vector<ll> ans(Q);
    vector<vector<int>> f(M + 1);
    for (int i = 0; i < Q; i++) {
        f[a[i]].push_back(i);
    }
    q = PST<ll, F, 0>(N);
    for (int i = M; i >= 0; i--) {
        if (i < M) {
            auto [c, p] = ch[i];
            q.upd(q.cpy(q.lst()), hld.pos[t[p]], 1);
        }
        for (int j : f[i]) {
            ans[j] = max(-1LL, X[j] - get(S[j], T[j], q.lst()));
        }
    }
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }
    return 6/22;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43352 KB Output is correct
2 Correct 22 ms 43356 KB Output is correct
3 Correct 23 ms 43348 KB Output is correct
4 Correct 23 ms 43356 KB Output is correct
5 Correct 30 ms 45404 KB Output is correct
6 Correct 33 ms 45404 KB Output is correct
7 Correct 31 ms 44880 KB Output is correct
8 Correct 36 ms 45652 KB Output is correct
9 Correct 34 ms 45660 KB Output is correct
10 Correct 34 ms 45648 KB Output is correct
11 Correct 36 ms 45652 KB Output is correct
12 Correct 33 ms 45560 KB Output is correct
13 Correct 31 ms 45884 KB Output is correct
14 Correct 31 ms 45656 KB Output is correct
15 Correct 31 ms 45652 KB Output is correct
16 Correct 32 ms 45652 KB Output is correct
17 Correct 32 ms 45656 KB Output is correct
18 Correct 34 ms 45648 KB Output is correct
19 Correct 30 ms 45592 KB Output is correct
20 Correct 30 ms 45648 KB Output is correct
21 Correct 31 ms 45904 KB Output is correct
22 Correct 31 ms 45788 KB Output is correct
23 Correct 36 ms 45548 KB Output is correct
24 Correct 33 ms 45748 KB Output is correct
25 Correct 33 ms 45660 KB Output is correct
26 Correct 35 ms 45584 KB Output is correct
27 Correct 30 ms 45652 KB Output is correct
28 Correct 32 ms 45524 KB Output is correct
29 Correct 29 ms 45724 KB Output is correct
30 Correct 34 ms 45648 KB Output is correct
31 Correct 35 ms 45912 KB Output is correct
32 Correct 39 ms 45496 KB Output is correct
33 Correct 30 ms 45908 KB Output is correct
34 Correct 30 ms 45648 KB Output is correct
35 Correct 36 ms 45656 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43352 KB Output is correct
2 Correct 33 ms 45648 KB Output is correct
3 Correct 39 ms 45492 KB Output is correct
4 Correct 34 ms 45652 KB Output is correct
5 Correct 1606 ms 177488 KB Output is correct
6 Correct 1974 ms 158852 KB Output is correct
7 Correct 1807 ms 144968 KB Output is correct
8 Correct 1356 ms 141188 KB Output is correct
9 Correct 1263 ms 147160 KB Output is correct
10 Correct 2584 ms 191696 KB Output is correct
11 Correct 2460 ms 191976 KB Output is correct
12 Correct 2503 ms 191704 KB Output is correct
13 Correct 2579 ms 191704 KB Output is correct
14 Correct 2524 ms 191716 KB Output is correct
15 Correct 1407 ms 199656 KB Output is correct
16 Correct 1394 ms 200216 KB Output is correct
17 Correct 1415 ms 199648 KB Output is correct
18 Correct 2428 ms 192112 KB Output is correct
19 Correct 2433 ms 191872 KB Output is correct
20 Correct 2399 ms 192076 KB Output is correct
21 Correct 1103 ms 192784 KB Output is correct
22 Correct 858 ms 192832 KB Output is correct
23 Correct 1208 ms 193324 KB Output is correct
24 Correct 901 ms 192776 KB Output is correct
25 Correct 1647 ms 193208 KB Output is correct
26 Correct 1848 ms 190296 KB Output is correct
27 Correct 1704 ms 193212 KB Output is correct
28 Correct 1074 ms 191436 KB Output is correct
29 Correct 931 ms 191380 KB Output is correct
30 Correct 1534 ms 191192 KB Output is correct
31 Correct 1655 ms 191188 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43500 KB Output is correct
2 Correct 30 ms 46164 KB Output is correct
3 Correct 29 ms 45904 KB Output is correct
4 Correct 31 ms 45916 KB Output is correct
5 Correct 768 ms 154596 KB Output is correct
6 Correct 676 ms 136952 KB Output is correct
7 Correct 1073 ms 171656 KB Output is correct
8 Correct 1497 ms 200400 KB Output is correct
9 Correct 1519 ms 200460 KB Output is correct
10 Correct 1450 ms 200392 KB Output is correct
11 Correct 1193 ms 201388 KB Output is correct
12 Correct 1115 ms 201332 KB Output is correct
13 Correct 1164 ms 198204 KB Output is correct
14 Correct 701 ms 199304 KB Output is correct
15 Correct 681 ms 199204 KB Output is correct
16 Correct 866 ms 199720 KB Output is correct
17 Correct 845 ms 199444 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43352 KB Output is correct
2 Correct 22 ms 43356 KB Output is correct
3 Correct 23 ms 43348 KB Output is correct
4 Correct 23 ms 43356 KB Output is correct
5 Correct 30 ms 45404 KB Output is correct
6 Correct 33 ms 45404 KB Output is correct
7 Correct 31 ms 44880 KB Output is correct
8 Correct 36 ms 45652 KB Output is correct
9 Correct 34 ms 45660 KB Output is correct
10 Correct 34 ms 45648 KB Output is correct
11 Correct 36 ms 45652 KB Output is correct
12 Correct 33 ms 45560 KB Output is correct
13 Correct 31 ms 45884 KB Output is correct
14 Correct 31 ms 45656 KB Output is correct
15 Correct 31 ms 45652 KB Output is correct
16 Correct 32 ms 45652 KB Output is correct
17 Correct 32 ms 45656 KB Output is correct
18 Correct 34 ms 45648 KB Output is correct
19 Correct 30 ms 45592 KB Output is correct
20 Correct 30 ms 45648 KB Output is correct
21 Correct 31 ms 45904 KB Output is correct
22 Correct 31 ms 45788 KB Output is correct
23 Correct 36 ms 45548 KB Output is correct
24 Correct 33 ms 45748 KB Output is correct
25 Correct 33 ms 45660 KB Output is correct
26 Correct 35 ms 45584 KB Output is correct
27 Correct 30 ms 45652 KB Output is correct
28 Correct 32 ms 45524 KB Output is correct
29 Correct 29 ms 45724 KB Output is correct
30 Correct 34 ms 45648 KB Output is correct
31 Correct 35 ms 45912 KB Output is correct
32 Correct 39 ms 45496 KB Output is correct
33 Correct 30 ms 45908 KB Output is correct
34 Correct 30 ms 45648 KB Output is correct
35 Correct 36 ms 45656 KB Output is correct
36 Correct 24 ms 43352 KB Output is correct
37 Correct 33 ms 45648 KB Output is correct
38 Correct 39 ms 45492 KB Output is correct
39 Correct 34 ms 45652 KB Output is correct
40 Correct 1606 ms 177488 KB Output is correct
41 Correct 1974 ms 158852 KB Output is correct
42 Correct 1807 ms 144968 KB Output is correct
43 Correct 1356 ms 141188 KB Output is correct
44 Correct 1263 ms 147160 KB Output is correct
45 Correct 2584 ms 191696 KB Output is correct
46 Correct 2460 ms 191976 KB Output is correct
47 Correct 2503 ms 191704 KB Output is correct
48 Correct 2579 ms 191704 KB Output is correct
49 Correct 2524 ms 191716 KB Output is correct
50 Correct 1407 ms 199656 KB Output is correct
51 Correct 1394 ms 200216 KB Output is correct
52 Correct 1415 ms 199648 KB Output is correct
53 Correct 2428 ms 192112 KB Output is correct
54 Correct 2433 ms 191872 KB Output is correct
55 Correct 2399 ms 192076 KB Output is correct
56 Correct 1103 ms 192784 KB Output is correct
57 Correct 858 ms 192832 KB Output is correct
58 Correct 1208 ms 193324 KB Output is correct
59 Correct 901 ms 192776 KB Output is correct
60 Correct 1647 ms 193208 KB Output is correct
61 Correct 1848 ms 190296 KB Output is correct
62 Correct 1704 ms 193212 KB Output is correct
63 Correct 1074 ms 191436 KB Output is correct
64 Correct 931 ms 191380 KB Output is correct
65 Correct 1534 ms 191192 KB Output is correct
66 Correct 1655 ms 191188 KB Output is correct
67 Correct 24 ms 43500 KB Output is correct
68 Correct 30 ms 46164 KB Output is correct
69 Correct 29 ms 45904 KB Output is correct
70 Correct 31 ms 45916 KB Output is correct
71 Correct 768 ms 154596 KB Output is correct
72 Correct 676 ms 136952 KB Output is correct
73 Correct 1073 ms 171656 KB Output is correct
74 Correct 1497 ms 200400 KB Output is correct
75 Correct 1519 ms 200460 KB Output is correct
76 Correct 1450 ms 200392 KB Output is correct
77 Correct 1193 ms 201388 KB Output is correct
78 Correct 1115 ms 201332 KB Output is correct
79 Correct 1164 ms 198204 KB Output is correct
80 Correct 701 ms 199304 KB Output is correct
81 Correct 681 ms 199204 KB Output is correct
82 Correct 866 ms 199720 KB Output is correct
83 Correct 845 ms 199444 KB Output is correct
84 Correct 1729 ms 176640 KB Output is correct
85 Correct 1767 ms 156712 KB Output is correct
86 Correct 1524 ms 126568 KB Output is correct
87 Correct 2827 ms 191812 KB Output is correct
88 Correct 2877 ms 191840 KB Output is correct
89 Correct 2964 ms 191708 KB Output is correct
90 Correct 2885 ms 191704 KB Output is correct
91 Correct 2941 ms 191716 KB Output is correct
92 Correct 1698 ms 197368 KB Output is correct
93 Correct 1620 ms 199048 KB Output is correct
94 Correct 2738 ms 192132 KB Output is correct
95 Correct 2815 ms 192068 KB Output is correct
96 Correct 2774 ms 191928 KB Output is correct
97 Correct 2895 ms 192024 KB Output is correct
98 Correct 1531 ms 192788 KB Output is correct
99 Correct 1554 ms 192860 KB Output is correct
100 Correct 1585 ms 192812 KB Output is correct
101 Correct 1567 ms 192764 KB Output is correct
102 Correct 1965 ms 190176 KB Output is correct
103 Correct 2083 ms 193056 KB Output is correct
104 Correct 1973 ms 190112 KB Output is correct
105 Correct 1160 ms 191280 KB Output is correct
106 Correct 1422 ms 191220 KB Output is correct
107 Correct 1523 ms 191268 KB Output is correct
108 Correct 1380 ms 191180 KB Output is correct