Submission #884948

#	Time	Username	Problem	Language	Result	Execution time	Memory
884948		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	253 ms	58832 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define endl '\n'
#define ll long long
#define int ll
#define pii pair <int, int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 1e18;

int n, q, x, y;
int a[N], b[N], sm[N][20], par[N][20];
vector<int> v[N];

void DFS(int node){
    for(int i = 1; i < 20; i++){
        par[node][i] = par[par[node][i - 1]][i - 1];
        sm[node][i] = sm[node][i - 1] + sm[par[node][i - 1]][i - 1];
    }
    for(int i : v[node]){
        par[i][0] = node;
        sm[i][0] = b[i];
        DFS(i);
    }
}

signed main() {
    io;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    stack<pii> s;
    s.push({INF, 0});
    for(int i = n; i > 0; i--){
        while(!s.empty() && s.top().first <= a[i]){
            s.pop();
        }
        int cur = s.top().second;
        v[cur].pb(i);
        s.push({a[i], i});
    }
    DFS(0);
    while(q--){
        cin >> x >> y;
        for(int i = 19; i >= 0; i--){
            if(sm[x][i] < y){
              //  cout << x << " " << y << " ----- " << sm[x][i] << "  ";
                y -= sm[x][i];
                x = par[x][i];

            }
        }
        cout << x << endl;
    }
}
/*
1 2 3 4 5 6     7
4 6 3 4 10 4    INF

5
8
9
12
16


0
101110
*/

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