Submission #404401

#	Time	Username	Problem	Language	Result	Execution time	Memory
404401		hiderr	Fountain (eJOI20_fountain)	C++14	100 / 100	219 ms	14916 KiB

fountain

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

const int MAX_N = 100000;
const int LOG_N = 17;
long long sum[MAX_N + 1]; int height[MAX_N + 1], last[MAX_N + 1];

const int NONE = 0;
int pointers[MAX_N + 1][LOG_N + 1];

int find_level(int r, long long v, long long required) {
    int i = 0; while(sum[pointers[r][i]] > required) i++;
    if(i == 0) return r;
    return find_level(pointers[r][i-1], v, required);
}


int main() {

    cin.tie(0); ios_base::sync_with_stdio(false);
    int n, q; cin >> n >> q;

    stack<pair<int, int>> mq; mq.push({ 0, NONE });

    for(int i = 1; i <= n; i++) { cin >> height[i] >> sum[i]; }
    for(int i = n; i >= 1; i--) {
        pair<int, int> t = mq.top();
        while (mq.top().second != NONE && mq.top().first <= height[i]) {
            mq.pop(); t = mq.top(); 
        }
        last[i] = t.second;
        mq.push({height[i], i});
    }

    for(int i = n; i >= 1; i--) {
        if(last[i] != NONE) {
            sum[i] += sum[last[i]]; pointers[i][0] = last[i];
            for(int j = 1; j <= LOG_N; j++) {
                int next_pointer = pointers[pointers[i][j-1]][j-1];
                if(next_pointer != NONE) pointers[i][j] = next_pointer;
                else break;
            }

        }
    }

    int r; long long v;
    for(int do_not_use_me = 0; do_not_use_me < q; do_not_use_me++) {
        cin >> r >> v;
        long long required = sum[r] - v;
        if(required < 0) { cout << 0 << '\n'; continue; }
        cout << find_level(r, v, required) << '\n';
    }

}

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