oj.uz

답안 #585281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585281 2022-06-28T14:16:01 Z algorithm16 Fountain (eJOI20_fountain) C++14
0 / 100
 309 ms 23348 KB 
#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int maxn = 1e5 + 7;

typedef pair <int, int> pii;

int n, q;
int c[maxn], d[maxn], v[maxn], r[maxn], par[maxn][21], ps[maxn];
set <pii> s;
vector <int> sus[maxn];

void pres (int x, int prf) {
	ps[x] = prf + c[x];
	if (sus[x].size() == 0) {
		return;
	}
	for (auto it : sus[x]) {
		pres(it, prf + c[x]);
	}
}

int main () {
	cin >> n >> q;
	
	for (int i = 1; i <= n; i++) {
		cin >> d[i] >> c[i];
		auto it = s.lower_bound({d[i], 0});
		if (it == s.begin()) {
			s.insert({d[i], i});
			continue;
		}
		do {
			--it;
			pii tr = *it;
			par[tr.S][0] = i;
			sus[i].push_back(tr.S);
			it = s.erase(it);
		} while (it != s.begin());
		s.insert({d[i], i});
	}
	
	auto it = s.begin();
	while (!s.empty()) {
		pii tr = *it;
		sus[0].push_back(tr.S);
		it = s.erase(it);
	}
	
	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= 20; k++) {
			par[i][k] = par[par[i][k-1]][k-1];
		}
	}
	
	pres(0, 0);
	
	/*
	for (int i = 1; i <= n; i++) {
		cout << ps[i] << "\n";
	}*/
	
	for (int i = 0; i < q; i++) {
		cin >> r[i] >> v[i];
		int tr = r[i];
		if (v[i] > ps[tr]) {
			cout << "0\n";
			continue;
		}
		for (int k = 20; k >= 0; k--) {
			int cur = ps[tr] - ps[par[tr][k]];
			if (v[i] > cur) {
				tr = par[tr][k];
				v[i] -= cur;
			}
		}
		cout << tr << "\n";
	}
	
	return 0;
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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