oj.uz

Submission #466695

# Submission time Handle Problem Language Result Execution time Memory
466695 2021-08-20T08:59:50 Z Clan328 Fountain (eJOI20_fountain) C++17
0 / 100
 1500 ms 39248 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define nL '\n'
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct node {
	int p, idx, c;
	ll d;
};

vector<node> G;
vector<vector<pair<int, ll>>> up;

void readInput(int n, int i) {
	ll d;
	int c;
	cin >> d >> c;

	if (i < n)
		readInput(n, i+1);

	G[i] = {i, i, c, d};

	int j = i+1;
	while (j > 0 && j <= n && G[i].d > G[j].d) {
		j = G[j].p;
	}

	if (j > n)
		j = 0;

	//cout << G.size() << nL;

	G[i].p = j;
}

int main() {
	#ifdef LOCAL
		freopen("io/input.txt", "r", stdin);
		freopen("io/output.txt", "w", stdout);
	#endif

	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, q;
	cin >> n >> q;

	G = vector<node>(n+1);
	readInput(n, 1);

	int LOG = log2(n);

	up = vector<vector<pair<int, ll>>>(n+1, vector<pair<int, ll>>(LOG));

	for (int v = n; v > 0; v--) {
		up[v][0] = {G[v].p, G[v].c+G[G[v].p].c};
		for (int j = 1; j < LOG; j++) {
			int p = up[up[v][j-1].first][j-1].first;
			up[v][j] = {p, up[v][j-1].second+up[p][j-1].second};
		}
	}

	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 0; j < LOG; j++)
	// 		cout << "(" << up[i][j].first << ", " << up[i][j].second << ") ";
	// 	cout << nL;
	// }

	while (q--) {
		int r;
		ll v;
		cin >> r >> v;

		while (v > 0 && r > 0) {
			if (v - G[r].c <= 0) {
				//cout << r << nL;
				break;
			}
			int lo = 0, hi = LOG-1, res = 0, mid;
			while (lo <= hi) {
				mid = (lo+hi)/2;
				if (up[r][mid].second >= v) {
					res = mid;
					hi = mid - 1;
				} else
					lo = mid + 1;
			}

			//cout << res << nL;

			v -= up[r][res].second;
			r = up[r][res].first;
		}

		cout << r << nL;
	}

	return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1533 ms 39248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -