제출 #641443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641443		Valaki2	Fountain (eJOI20_fountain)	C++14	100 / 100	255 ms	22784 KiB

fountain

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

#define ll long long
#define pb push_back

const int inf = 1e9 + 42;
const int maxn = 1e5;
const int maxlogn = 20;

int n, q;
int diam[1 + maxn];
int cap[1 + maxn];
int par[1 + maxn];
int bl_pos[1 + maxn][maxlogn];
int bl_amount[1 + maxn][maxlogn];

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> diam[i] >> cap[i];
    }
    diam[0] = inf;
    par[0] = 0;
    stack<int> s;
    s.push(0);
    for(int i = n; i >= 1; i--) {
        while(diam[s.top()] <= diam[i]) {
            s.pop();
        }
        par[i] = s.top();
        s.push(i);
    }
    for(int i = 0; i <= n; i++) {
        bl_pos[i][0] = par[i];
        bl_amount[i][0] = cap[i];
    }
    for(int j = 1; j < maxlogn; j++) {
        for(int i = 0; i <= n; i++) {
            bl_pos[i][j] = bl_pos[bl_pos[i][j - 1]][j - 1];
            bl_amount[i][j] = bl_amount[i][j - 1] + bl_amount[bl_pos[i][j - 1]][j - 1];
        }
    }
    for(int qi = 1; qi <= q; qi++) {
        int pos, val;
        cin >> pos >> val;
        for(int i = maxlogn - 1; i >= 0; i--) {
            if(val > bl_amount[pos][i]) {
                val -= bl_amount[pos][i];
                pos = bl_pos[pos][i];
            }
        }
        cout << pos << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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