oj.uz

답안 #466701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466701 2021-08-20T10:13:00 Z Clan328 Fountain (eJOI20_fountain) C++17
0 / 100
 338 ms 34624 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;
typedef vector<pll> vpll;

vvl up;
vvl sum;

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);

	ll n, q;
	cin >> n >> q;
	vpll input(n+1);
	for (int i = 1; i <= n; i++)
		cin >> input[i].first >> input[i].second;

	ll LOG = log2(n);
	up = vvl(n+2, vl(LOG+1));
	sum = vvl(n+2, vl(LOG+1));
	
	stack<ll> stk;
	for (int i = n; i > 0; i--) {
		while (!stk.empty() && input[stk.top()].first <= input[i].first)
			stk.pop();
		if (!stk.empty())
			up[i][0] = stk.top();
		else
			up[i][0] = n+1;
		sum[i][0] = input[i].second;
		stk.push(i);
	}

	sum[n+1][0] = 1e18;
	for (ll j = 1; j < LOG; j++) {
		sum[n+1][j] = 1e18;
		for (ll v = 1; v <= n; v++) {
			up[v][j] = up[up[v][j-1]][j-1];
			sum[v][j] = sum[v][j-1] + sum[up[v][j-1]][j-1];
		}
	}

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

		for (ll i = LOG-1; i >= 0; i--) {
			if (sum[r][i] < v) {
				v -= sum[r][i];
				r = up[r][i];
			}
		}

		cout << (r <= n? r : 0) << nL;
	}

	return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 2 ms 576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 338 ms 34624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 2 ms 576 KB Output isn't correct
6 Halted 0 ms 0 KB -