Submission #404376

#	Time	Username	Problem	Language	Result	Execution time	Memory
404376		hiderr	Fountain (eJOI20_fountain)	C++17	0 / 100	101 ms	12648 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 = sum[r] - v;
    if(required < 0) { return 0; }
    int i = 0;
    while(sum[pointers[r][0]] > required) {
        if(sum[pointers[r][i]] < required) { r = pointers[r][i-1]; i++; }
        else i++;
    }
    return r;
}


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;
        cout << find_level(r, v) << '\n';
    }

}

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