oj.uz

Submission #466506

# Submission time Handle Problem Language Result Execution time Memory
466506 2021-08-19T13:48:27 Z FulopMate Fountain (eJOI20_fountain) C++17
100 / 100
 698 ms 38128 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(c) (c).begin(), (c).end()
#define MIN(a, b) ((a) = min((a), (b)))
#define MAX(a, b) ((a) = max((a), (b)))

const ll MOD = 1e9+7;
const int abc = 'z'-'a'+1;

int n, q;
vector<ll> d, c;
vector<ll> p;
vector<array<pair<ll,int>, 19>> v;
// v[i][j] = i. medencebol indulva 2^j-t lemenve (a faban) {mennyi viz kell, melyik medence}
// v[n][barmi] = {1e9+1, n};

int query(int i, ll w){
    if(w <= c[i]) return i;
    int j = 0;
    while(v[i][j].first < w)j++;
    j--;
    return query(v[i][j].second, w-v[i][j].first);
}

void solve(){
    cin>>n>>q;
    d.resize(n); c.resize(n);
    for(int i = 0; i < n; i++){
        cin>>d[i]>>c[i];
    }
    p.assign(n, 0);
    stack<int> s;
    for(int i = n-1; i >= 0; i--){
        while(!s.empty() && d[s.top()] <= d[i]){
            s.pop();
        }
        if(s.empty()) p[i] = n;
        else p[i] = s.top();
        s.push(i);
    }
    v.assign(n+1, array<pair<ll,int>, 19>());
    for(int i = 0; i < 19; i++){
        v[n][i] = {1e17+1, n};
    }
    for(int i = n-1; i >= 0; i--){
        if(p[i] == n){
            for(int j = 0; j < 19; j++){
                v[i][j] = {1e17+1, n};
            }
            continue;
        }
        v[i][0] = {c[i], p[i]};
        for(int j = 1; j < 19; j++){
            if(v[i][j-1].second == n){
                v[i][j] = {1e17+1, n};
                continue;
            }
            if(v[ v[i][j-1].second ][j-1].second == n){
                v[i][j] = {1e17+1, n};
                continue;
            }
            v[i][j].first = v[i][j-1].first + v[ v[i][j-1].second ][j-1].first;
            v[i][j].second = v[ v[i][j-1].second ][j-1].second;
        }
    }
    while(q--){
        int a, b; cin>>a>>b; a--;
        int r = query(a, b);
        cout<<(r+1)%(n+1)<<endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int _t;
    _t = 1;
    while(_t--){
        solve();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 33392 KB Output is correct
2 Correct 456 ms 32588 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 5 ms 588 KB Output is correct
8 Correct 429 ms 33392 KB Output is correct
9 Correct 456 ms 32588 KB Output is correct
10 Correct 4 ms 584 KB Output is correct
11 Correct 238 ms 20376 KB Output is correct
12 Correct 698 ms 38128 KB Output is correct
13 Correct 576 ms 37424 KB Output is correct
14 Correct 455 ms 36432 KB Output is correct
15 Correct 427 ms 36700 KB Output is correct