제출 #1180857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180857		aguss	Fountain (eJOI20_fountain)	C++20	100 / 100	224 ms	51656 KiB

fountain

#include <bits/stdc++.h>

#define dbg(x) cerr << #x << ": " << x << '\n';
#define dbgv(v) cerr << #v << ": "; for(auto &el : v) cerr << el << " "; cerr << '\n';

using namespace std;
using ll = long long;

bool test_cases = 0;
vector<ll> diam, vol, vis;
vector<vector<ll>> adj, up, up2;
int n, q, k = 18;
void dfs(int node, int prev = -1){
    up[node][0] = (prev == -1 ? 0 : vol[prev]);
    up2[node][0] = (prev == -1 ? node : prev);
    vis[node] = 1;
    for(int i = 1; i <= k; i++){
        up2[node][i] = up2[up2[node][i - 1]][i - 1];
        up[node][i] = up[up2[node][i - 1]][i - 1] + up[node][i - 1];
    }
    for(ll &i : adj[node]){
        if(i == prev) continue;
        dfs(i, node);
    }
}
int query(int node, ll vol2){
    ll sum = vol2 - vol[node];
    if(sum <= 0){
        return node + 1;
    }
    for(int i = k; i >= 0; i--){
        if(sum - up[node][i] > 0){
            sum -= up[node][i];
            node = up2[node][i];
        } 
    }
    if(sum - up[node][0] > 0){
        return 0;
    }
    return up2[node][0] + 1;
}
void solve(){
    cin >> n >> q;
    diam.assign(n, 0);
    vis.assign(n, 0);
    vol.assign(n, 0);
    adj.assign(n, vector<ll>());
    up.assign(n, vector<ll>(k + 1));
    up2.assign(n, vector<ll>(k + 1));
    vector<pair<int, int>> idk;
    for(int i = 0; i < n; i++){
        cin >> diam[i] >> vol[i];
        idk.push_back({diam[i], i});
    } 
    stack<pair<int, int>> build;
    build.push({diam.back(), diam.size() - 1});
    for(int i = n - 1; i >= 0; i--){
        while(!build.empty() and diam[i] >= build.top().first){
            build.pop();
        }
        if(!build.empty()){ 
            adj[i].push_back(build.top().second);
            adj[build.top().second].push_back(i);
        }
        build.push({diam[i], i});
    }
    sort(idk.rbegin(), idk.rend());
    for(int i = 0; i < n; i++){
        if(vis[idk[i].second]) continue;
        dfs(idk[i].second);
    }
    while(q--){
        int start_node;
        ll lit;
        cin >> start_node >> lit;
        cout << query(--start_node, lit) << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    if(test_cases){
        int t;
        cin >> t;
        for(int i = 0; i < t; i++){
            solve();
        }
        return 0;
    }
    solve();
    return 0;
}

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