Submission #465838

#	Time	Username	Problem	Language	Result	Execution time	Memory
465838		nemethm	Fountain (eJOI20_fountain)	C++17	100 / 100	1014 ms	21956 KiB

fountain

#include <iostream>
#include <list>
#include <algorithm>
#include <queue>
#include <vector>
#include <limits>
#include <set>
#include <numeric>
#include <string>
#include <assert.h>
#include <map>
#include <cmath>
#include <stack>
#include <cstring>
#include <stack>
#pragma warning(disable : 4996)
using namespace std;
using ll = long long int;
const ll inf = numeric_limits<ll>::max();
const ll mod = 1e9+7;
void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

int dp[100100][25] = { 0 };
int jump(int node, int d) {
	for (int i = 0; i < 32; ++i) {
		if ((d >> i) & 1) {
			node = dp[node][i];
		}
	}
	return node;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(9);
	int n, q;
	cin >> n >> q;
	vector<pair<int, int>> v(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> v[i].first >> v[i].second;
	}
	stack<int> s;
	vector<vector<int>> gt(n + 1);
	for (int i = 1; i <= n; ++i) {
		while (!s.empty() && v[s.top()].first < v[i].first) {
			dp[s.top()][0] = i;
			gt[i].push_back(s.top());
			s.pop();
		}
		s.push(i);
	}
	vector<int> pre(n + 1);
	while (!s.empty()) {
		int a = s.top();
		s.pop();
		pre[a] = pre[dp[a][0]] + v[a].second;
		for (auto i : gt[a]) {
			s.push(i);
		}
	}
	for (int i = 1; i < 20; ++i) {
		for (int j = 1; j <= n; ++j) {
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}
	while (q--) {
		int r, v;
		cin >> r >> v;
		if (pre[r] >= v) {

			int tav = 100000, node = r;
			while (pre[dp[node][0]] > pre[r] - v) {
				int m = jump(node, (tav + 1) / 2);
				if (pre[m] > pre[r] - v) {
					node = m;
				}
				tav = (tav + 1) / 2;
			}
			cout << node << "\n";
		}
		else {
			cout << 0 << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

fountain.cpp:16: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
   16 | #pragma warning(disable : 4996)
      | 
fountain.cpp: In function 'void setIO(std::string)':
fountain.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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