/*
____ _ _ _ _ _ _ _ _ _____ _ _
| _ \ (_) | | (_) | | (_) | | | | (_) / ____| | (_)
| |_) | ___ _ ___| |__ ___ _ __ _ ___ __ _ ___| | __ _ ___ ___ _ ___ _ __ _ __ ___ | |__ | | ___ _ __ ___ _ _ __ | | | |__ _ _ __ __ _
| _ < / _ \ |/ __| '_ \ / _ \ '_ \ | / __| / _` | / __| |/ _` / __/ __| |/ __| | '_ \| '__/ _ \| '_ \| |/ _ \ '_ ` _ \ | | '_ \ | | | '_ \| | '_ \ / _` |
| |_) | __/ | (__| | | | __/ | | | | \__ \ | (_| | | (__| | (_| \__ \__ \ | (__ | |_) | | | (_) | |_) | | __/ | | | | | | | | | | | |____| | | | | | | | (_| |
|____/ \___|_|\___|_| |_|\___|_| |_| |_|___/ \__,_| \___|_|\__,_|___/___/_|\___| | .__/|_| \___/|_.__/|_|\___|_| |_| |_| |_|_| |_| \_____|_| |_|_|_| |_|\__,_|
| |
|_|
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << " is " << x << "\n";
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define linebreak cout << "---------------------------------------------------------\n";
const int MS = 1e5, LOG = 20;
int twok[MS][LOG], d[MS], c[MS], nearest[MS], pref[MS];
vector<int> adj[MS];
void dfs(int x, int par) {
for (int k = 0; k < LOG; k++) {
if (twok[x][k] == -1) break;
if (twok[twok[x][k]][k] != -1) {
twok[x][k+1] = twok[twok[x][k]][k];
}
}
for (auto u : adj[x]) {
if (u == par) continue;
twok[u][0] = x;
dfs(u, x);
}
}
int sum(int a, int b) {
if (twok[a][0] == -1) return pref[b];
return pref[b]-pref[twok[a][0]];
}
void solve() {
int n, q; cin >> n >> q;
d[0] = 1e18; c[0] = 1e18;
for (int i = 1; i <= n; i++) cin >> d[i] >> c[i];
vector<int> v;
for (int i = 1; i <= n; i++) {
if (v.empty()) {v.push_back(i); continue;}
while (!v.empty() and d[v.back()] < d[i]) {
nearest[v.back()] = i;
v.pop_back();
}
v.push_back(i);
}
for (auto i : v) nearest[i] = 0;
for (int i = 1; i <= n; i++) {
adj[i].push_back(nearest[i]);
adj[nearest[i]].push_back(i);
}
memset(twok, -1, sizeof(twok));
dfs(0, -1);
int vis[MS];
queue<int> qq;
qq.push(0);
pref[0] = 0;
memset(vis, 0, sizeof(vis));
vis[0] = 1;
while (!qq.empty()) {
int cur = qq.front();
qq.pop();
for (auto v : adj[cur]) {
if (!vis[v]) {
vis[v] = 1;
qq.push(v);
pref[v] = pref[cur]+c[v];
}
}
}
while (q--) {
int r, v;
cin >> r >> v;
if (c[r] >= v) {
cout << r << '\n'; continue;
}
int original = r;
for (int k = LOG-1; k >= 0; k--) {
int temp = -1;
if (r != -1) temp = twok[r][k];
if (temp != -1 and sum(temp, original) < v) {
r = temp;
}
}
if (r == -1 or twok[r][0] == -1) cout << 0 << '\n';
else cout << twok[r][0] << '\n';
}
}
int32_t main() {
hehe
int tc = 1;
//cin >> tc;
while (tc--) {solve();}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
22364 KB |
Output is correct |
| 2 |
Correct |
5 ms |
22364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
22360 KB |
Output is correct |
| 4 |
Correct |
6 ms |
22360 KB |
Output is correct |
| 5 |
Correct |
6 ms |
22364 KB |
Output is correct |
| 6 |
Correct |
7 ms |
22364 KB |
Output is correct |
| 7 |
Correct |
6 ms |
22384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
31348 KB |
Output is correct |
| 2 |
Correct |
325 ms |
31676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
22364 KB |
Output is correct |
| 2 |
Correct |
5 ms |
22364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
22360 KB |
Output is correct |
| 4 |
Correct |
6 ms |
22360 KB |
Output is correct |
| 5 |
Correct |
6 ms |
22364 KB |
Output is correct |
| 6 |
Correct |
7 ms |
22364 KB |
Output is correct |
| 7 |
Correct |
6 ms |
22384 KB |
Output is correct |
| 8 |
Correct |
204 ms |
31348 KB |
Output is correct |
| 9 |
Correct |
325 ms |
31676 KB |
Output is correct |
| 10 |
Correct |
6 ms |
22360 KB |
Output is correct |
| 11 |
Correct |
73 ms |
26432 KB |
Output is correct |
| 12 |
Runtime error |
51 ms |
52308 KB |
Execution killed with signal 11 |
| 13 |
Halted |
0 ms |
0 KB |
- |
