oj.uz

Submission #1050100

# Submission time Handle Problem Language Result Execution time Memory
1050100 2024-08-09T07:21:28 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 143 ms 32084 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int nArr, numQuery;
#define MAX                 100005
#define LOG                 18
pair<int, int> A[MAX];

int up[MAX][LOG], sm[MAX][LOG];


void process(void){
    cin >> nArr >> numQuery;
    for (int i = 1; i <= nArr; ++i){
        cin >> A[i].first >> A[i].second;
    }

    stack<int> st; st.push(nArr + 1);
    A[nArr + 1].first = INF;
    for (int i = nArr; i >= 1; --i){
        while(st.size() && A[i].first >= A[st.top()].first) st.pop();

        up[i][0] = st.top();
        sm[i][0] = A[i].second;
        st.push(i);
    }
    for (int i = 1; i < LOG; ++i){
        for (int u = 1; u <= nArr; ++u) {
            up[u][i] = up[up[u][i - 1]][i - 1];
            sm[u][i] = sm[u][i - 1] + sm[up[u][i - 1]][i - 1];
        }
    }


    for (int i = 1; i <= numQuery; ++i){
        int p, v; cin >> p >> v;
        for (int l = LOG - 1; l >= 0; --l){
            if (up[p][l] != 0 && (v - sm[p][l] > 0)){
                v -= sm[p][l];
                p = up[p][l];
            }
        }
        cout << (p == nArr + 1 ? 0 : p) << '\n';
    }
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 31480 KB Output is correct
2 Correct 104 ms 31508 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 100 ms 31480 KB Output is correct
9 Correct 104 ms 31508 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 34 ms 21880 KB Output is correct
12 Correct 143 ms 32084 KB Output is correct
13 Correct 133 ms 31420 KB Output is correct
14 Correct 88 ms 31240 KB Output is correct
15 Correct 65 ms 31224 KB Output is correct