oj.uz

답안 #736143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736143 2023-05-05T09:04:41 Z Toxtaq Fountain (eJOI20_fountain) C++17
100 / 100
 696 ms 34352 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 = 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
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 28464 KB Output is correct
2 Correct 482 ms 29264 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 478 ms 28464 KB Output is correct
9 Correct 482 ms 29264 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 151 ms 17484 KB Output is correct
12 Correct 696 ms 34352 KB Output is correct
13 Correct 387 ms 33456 KB Output is correct
14 Correct 305 ms 32644 KB Output is correct
15 Correct 261 ms 33012 KB Output is correct