Submission #632043

#	Time	Username	Problem	Language	Result	Execution time	Memory
632043		gagik_2007	Fountain (eJOI20_fountain)	C++17	100 / 100	691 ms	52528 KiB

fountain

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef double ld;
typedef ll itn;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll SAFEINF = 1e12;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;

struct Vaz {
	int ind;
	ll c;
	ll d;
	int nxt;
	Vaz(int i, int vv, int dd) {
		ind = i;
		c = vv;
		d = dd;
		nxt = 0;
	}
};

vector<Vaz>a;
vector<pair<int,int>>g[200007];
ll dp[200007][20];
ll up[200007][20];
ll lg;

void dfs(int v, int par = 0, ll val = SAFEINF) {
	//cout << v << endl;
	dp[v][0] = val;
	up[v][0] = par;
	for (int i = 0; i < g[v].size(); i++) {
		dfs(g[v][i].ff, v, g[v][i].ss);
	}
}

void calc() {
	for (int i = 1; i <= lg; i++) {
		for (int j = 0; j <= n; j++) {
			dp[j][i] = dp[j][i - 1] + dp[up[j][i - 1]][i - 1];
			up[j][i] = up[up[j][i - 1]][i - 1];
		}
	}
}

ll get_ans(int v, int c) {
	if (c <= 0)return v;
	for (int i = lg; i >= 0; i--) {
		//cout << v << " " << i << endl;
		if (c - dp[v][i] > 0) {
			c -= dp[v][i];
			v = up[v][i];
			if (v == 0)return v;
		}
	}
	return up[v][0];
}

int main() {
	cin >> n >> m;
	lg = ceil(log2(n));
	Vaz vaz(0, 0, 0);
	a.push_back(vaz);
	for (int i = 1; i <= n; i++) {
		ll x, y; cin >> x >> y;
		Vaz vaz(i, y, x);
		a.push_back(vaz);
	}
	set<pair<int, int>>cur;
	vector<pair<int, int>>to_del;
	for (int i = 1; i <= n; i++) {
		for (auto it = cur.begin(); it != cur.end(); it++) {
			if ((*it).ff < a[i].d) {
				a[(*it).ss].nxt = i;
				to_del.push_back((*it));
			}
			else break;
		}
		for (auto x : to_del) {
			cur.erase(x);
		}
		to_del.clear();
		cur.insert({ a[i].d,i });
	}
	for (int i = 1; i <= n; i++) {
		//cout << a[i].nxt << "->" << i << endl;
		g[a[i].nxt].push_back({ i,a[a[i].nxt].c });
	}
	dfs(0);
	calc();
	/*for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= lg; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= lg; j++) {
			cout << up[i][j] << " ";
		}
		cout << endl;
	}*/
	for (int i = 0; i < m; i++) {
		ll v, r;
		cin >> r >> v;
		v -= a[r].c;
		cout << get_ans(r, v) << endl;
	}
}

Compilation message (stderr)

fountain.cpp: In function 'void dfs(int, int, ll)':
fountain.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < g[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~

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