oj.uz

Submission #404407

# Submission time Handle Problem Language Result Execution time Memory
404407 2021-05-14T11:34:31 Z hiderr Fountain (eJOI20_fountain) C++14
100 / 100
 213 ms 11128 KB 
#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--) {
        sum[i] += sum[last[i]]; pointers[i][0] = last[i];
        for(int j = 1; j <= LOG_N; j++) {
            pointers[i][j] = pointers[pointers[i][j-1]][j-1];
        }
    }

    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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 9928 KB Output is correct
2 Correct 162 ms 9540 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 181 ms 9928 KB Output is correct
9 Correct 162 ms 9540 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 67 ms 5820 KB Output is correct
12 Correct 213 ms 11128 KB Output is correct
13 Correct 171 ms 10356 KB Output is correct
14 Correct 118 ms 10180 KB Output is correct
15 Correct 103 ms 10132 KB Output is correct