제출 #1312489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312489		syanvu	Fountain (eJOI20_fountain)	C++20	100 / 100	249 ms	47080 KiB

fountain

// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e5 + 1, inf = 1e9, mod = 998244353;

vector<int> g[N];
int up[N][21], sup[N][21], tin[N], tout[N], timer;
int d[N], c[N];

void dfs(int v, int p){
    up[v][0] = p;
    sup[v][0] = c[p];
    for(int i = 1; i < 20; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
        sup[v][i] = sup[v][i - 1] + sup[up[v][i - 1]][i - 1];
    }
    for(int to : g[v]){
        if(to == p) continue;
        dfs(to, v);
    }
}

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> d[i] >> c[i];
    }
    /*
    ..x.....x
    123456789
      |    |
    */
    stack<int> st;
    vector<int> root;
    for(int i = n; i >= 1; i--){
        while(st.size() && d[st.top()] <= d[i]) st.pop();
        if(st.size()){
            g[st.top()].push_back(i);
        }
        else g[n + 1].push_back(i);
        st.push(i);
    }
    dfs(n + 1, n + 1);
    while(q--){
        int v, s;
        cin >> v >> s;
        if(c[v] >= s){
            cout << v << '\n';
            continue;
        }
        s -= c[v];
        for(int i = 19; i >= 0; i--){
            if(sup[v][i] < s){
                s -= sup[v][i];
                v = up[v][i];
            }
        }
        s -= sup[v][0];
        v = up[v][0];
        if(s > 0 || v > n) cout << 0 << '\n';
        else cout << v << '\n';
    }
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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