#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
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++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5160 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5332 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5332 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
458 ms |
47260 KB |
Output is correct |
| 2 |
Correct |
510 ms |
45900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5160 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5332 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5332 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5332 KB |
Output is correct |
| 8 |
Correct |
458 ms |
47260 KB |
Output is correct |
| 9 |
Correct |
510 ms |
45900 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5400 KB |
Output is correct |
| 11 |
Correct |
287 ms |
28036 KB |
Output is correct |
| 12 |
Correct |
691 ms |
52528 KB |
Output is correct |
| 13 |
Correct |
576 ms |
47200 KB |
Output is correct |
| 14 |
Correct |
519 ms |
45716 KB |
Output is correct |
| 15 |
Correct |
557 ms |
48744 KB |
Output is correct |
