Submission #1037246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037246		0npata	Two Currencies (JOI23_currencies)	C++17	10 / 100	4678 ms	1048576 KiB

currencies

#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define int long long

const int MXM = 1<<17;
const int MXQ = 100'005;
const int MXN = 1<<17;

#define ptr shared_ptr

struct Node {
	ptr<Node> left;
	ptr<Node> right;
	int sum = 0;
	int cnt = 0;

	ptr<Node> get_left() {
		ptr<Node> res(new Node{});
		if(left) *res = *left;
		left = res;
		return left;
	}
	ptr<Node> get_right() {
		ptr<Node> res(new Node{});
		if(right) *res = *right;
		right = res;
		return right;
	}

	void update(int l, int r, int add) {
		_update(l, r, add, 0, MXN);
	}

	void _update(int l, int r, int add, int tl, int tr) {
		if(tl >= r || tr <= l) {
			return;
		}
		if(tl >= l && tr <= r) {
			sum += add;
			cnt++;
			return;
		}
		int tm = (tl+tr)/2;
		get_left()->_update(l, r, add, tl, tm);
		get_right()->_update(l, r, add, tm, tr);
	}

	pair<int, int> query(int i) {
		return _query(i, 0, MXN);
	}

	void push() {
		get_left()->sum += sum;
		get_left()->cnt += cnt;
		get_right()->sum += sum;
		get_right()->cnt += cnt;
		sum = 0;
		cnt = 0;
	}

	pair<int, int> _query(int i, int tl, int tr) {
		if(tl+1 == tr) {
			assert(tl == i);
			return {sum, cnt};
		}
		push();
		int tm = (tl+tr)/2;
		if(i<tm) {
			return get_left()->_query(i, tl, tm);
		}
		else {
			return get_right()->_query(i, tm, tr);
		}
	}
};

Node pers_st[MXM];

int in[MXN];
int out[MXN];
int depth[MXN];
int jmp[MXN][20];

vec<int> tree[MXN];

int t = 0;

void dfs1(int u, int p = -1) {
	jmp[u][0] = p;
	for(int i = 1; i<20; i++) {
		if(jmp[u][i-1] == -1) {
			jmp[u][i] = -1;
			continue;
		}
		jmp[u][i] = jmp[jmp[u][i-1]][i-1];
	}

	in[u] = t++;
	for(int v : tree[u]) {
		if(v == p) continue;
		depth[v] = depth[u]+1;
		dfs1(v, u);
	}
	out[u] = t;
}

int lca(int u, int v) {
	if(depth[u] < depth[v]) swap(u, v);
	for(int i = 0; i<20; i++) {
		if((depth[u]-depth[v]) & (1<<i)) {
			u = jmp[u][i];
		}
	}
	if(u == v) return u;
	for(int i = 19; i>=0; i--) {
		if(jmp[u][i] != jmp[v][i]) {
			u = jmp[u][i];
			v = jmp[v][i];
		}
	}
	return jmp[u][0];
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, M, Q;
	cin >> N >> M >> Q;

	vec<pair<int, int>> edges(N-1);

	for(int i = 0; i<N-1; i++) {
		int u, v;
		cin >> u >> v;
		u--;v--;
		tree[u].push_back(v);
		tree[v].push_back(u);
		edges[i] = {u, v};
	}

	dfs1(0);

	vec<pair<int, int>> cs(M);

	for(int i = 0; i<M; i++) {
		int ei, c;
		cin >> ei >> c;
		ei--;
		cs[i] = {c, ei};
	}
	sort(cs.begin(), cs.end());
	for(int i = 1; i<=M; i++) {
		pers_st[i] = pers_st[i-1];
		auto [c, ei] = cs[i-1];
		auto [u, v] = edges[ei];
		if(depth[u] < depth[v]) swap(u, v);

		pers_st[i].update(in[u], out[u], c);

		//cerr << "INSERTING: " << in[u] << ' ' << out[u]  << ' ' << c << '\n';
	}



	for(int i = 0; i<Q; i++) {
		int u, v, g, s;
		cin >> u >> v >> g >> s;
		u--;v--;

		int w = lca(u, v);

		//cerr << u << ' ' << v << ' ' << w << '\n';

		auto eval = [&](int k) {
			auto [a1, a2] = pers_st[k].query(in[u]);
			auto [b1, b2] = pers_st[k].query(in[v]);
			auto [c1, c2] = pers_st[k].query(in[w]);
		/// << a2 << ' ' << b2 << ' ' << c2 << '\n';

			return pair<int, int>{a1+b1-2*c1, a2+b2-2*c2};
		};

		int l = 0;
		int r = M+1;
		while(l+1<r) {
			int m = (l+r)/2;
			auto res = eval(m);
			if(res.first > s) {
				r = m;
			}
			else {
				l = m;
			}
		}
		int cnt = eval(l).second;
		int tot_cnt = eval(M).second;
		if(tot_cnt-cnt > g) {
			cout << -1 << '\n';
		}
		else {
			cout << g-(tot_cnt-cnt) << '\n';
		}
	}

}

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