제출 #1012952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012952		vjudge1	Fountain (eJOI20_fountain)	C++14	100 / 100	204 ms	42600 KiB

fountain

#include <bits/stdc++.h>
#define res register int
#define int long long
using namespace std;
const int N = 200005, LOGN = 20;
int n, m, d[N], c[N], f[LOGN][N], tot, sum[LOGN][N];
int ksm (int x, int y) {
	int s = 1;
	for (; y; x = x * x, y >>= 1)
		if (y & 1) s = s * x;
	return s;
}
struct STK {
	int val, id;
} st[N];
signed main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	for (res i = 1; i <= n; i ++) cin >> d[i] >> c[i];
	for (res i = 1; i <= n; i ++) {
		while (tot && st[tot].val < d[i])
			f[0][st[tot].id] = i, sum[0][st[tot].id] = c[i], tot --;
        st[++ tot] = {d[i], i};
	}
	for (res j = 1; j < LOGN; j ++)
		for (res i = 1; i <= n; i ++) {
			f[j][i] = f[j - 1][f[j - 1][i]];
			sum[j][i] = sum[j - 1][i] + sum[j - 1][f[j - 1][i]];
		}
	for (res i = 1, x, v; i <= m; i ++) {
		cin >> x >> v;
		v -= c[x];
		for (res j = LOGN - 1; ~j; j --)
			if (sum[j][x] && v > sum[j][x]) v -= sum[j][x], x = f[j][x];
		if (v > 0) x = f[0][x];
		cout << x << '\n';
	}
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40