oj.uz

답안 #736133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736133 2023-05-05T09:00:27 Z Toxtaq Fountain (eJOI20_fountain) C++17
0 / 100
 506 ms 28236 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int>d, c; /// diameter and capacity
vector<vector<long long>>table, calc;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    d.resize(n + 1);
    c.resize(n + 1);
    vector<int>next(n + 1), LOG(n + 1);
    LOG[1] = 0;
    for(int i = 2;i <= n;++i)LOG[i] = LOG[i / 2] + 1;
    table.resize(LOG[n] + 1);
    calc.resize(LOG[n] + 1);
    for(int i = 0;i <= LOG[n];++i){
        table[i].resize(n + 1);
        calc[i].resize(n + 1);
    }
    d[0] = 2e9;
    c[0] = 2e9;
    for(int i = 1;i <= n;++i){
        cin >> d[i] >> c[i];
    }
    stack<int>st;
    st.push(0);
    for(int i = n;i >= 1;--i){
        while(d[st.top()] <= d[i]){
            st.pop();
        }
        next[i] = st.top();
        st.push(i);
    }
    table[0][0] = 0;
    for(int i = 0;i <= n;++i){
        table[0][i] = next[i];
        calc[0][i] = c[next[i]];
    }
    for(int i = 1;i <= LOG[n];++i){
        for(int j = 0;j <= n;++j){
            table[i][j] = table[i - 1][table[i - 1][j]];
            calc[i][j] = calc[i - 1][j] + calc[i - 1][table[i - 1][j]];
        }
    }
    while(q--){
        int node, v;
        cin >> node >> v;
        int l = 0, r = n + 1, ans = 0;
        while(r >= l){
            int mid = (l + r) >> 1;
            int cpy = mid, cpyn = node;
            long long C = 1 + c[node];
//            cout << "MID: " << mid << ": \n";
            for(int i = LOG[n];i >= 0;--i){
                if(cpy >= (1 << i)){
                    cpy -= (1 << i);
                    C += calc[i][cpyn];
                    cpyn = table[i][cpyn];
                    if(C >= v){
                        break;
                    }
//                    cout << "NODE: " << cpyn << "\n";
                }
            }
//            cout << C << "\n\n";
            if(C >= v){
                ans = cpyn;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        cout << ans << '\n';
    }
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 506 ms 28236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -