oj.uz

Submission #465838

# Submission time Handle Problem Language Result Execution time Memory
465838 2021-08-16T21:52:55 Z nemethm Fountain (eJOI20_fountain) C++17
100 / 100
 1014 ms 21956 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 16664 KB Output is correct
2 Correct 596 ms 18720 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 520 ms 16664 KB Output is correct
9 Correct 596 ms 18720 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 212 ms 11148 KB Output is correct
12 Correct 1014 ms 21956 KB Output is correct
13 Correct 512 ms 20484 KB Output is correct
14 Correct 390 ms 19584 KB Output is correct
15 Correct 265 ms 18700 KB Output is correct