Submission #772685

#	Time	Username	Problem	Language	Result	Execution time	Memory
772685		PAndaS	Fountain (eJOI20_fountain)	C++14	60 / 100	1587 ms	42196 KiB

fountain

#include<iostream>
#include<vector>

#define K 20

using namespace std;

vector<vector<long>> up, sum;

long f(long u, long x){
    long res = 0;
    for(long i = 0; x; i++)if(x & (1 << i)){
        res += sum[u][i];
        u = up[u][i];
        x -= (1 << i);
        if(u == -1) break;
    }
    return res;
}

long jump(int u, int x){
    for(long i = 0; x; i++) if(x & (1 << i)){
        u = up[u][i];
        x -= (1 << i);
        if(u == -1) break;
    }
    return u;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long n, q; cin >> n >> q;
    vector<long> c(n), d(n);
    for(long i = 0; i < n; i++) cin >> d[i] >> c[i];
    up.resize(n, vector<long>(K, -1));
    for(long i = 0; i < n; i++) for(long j = i + 1; j < n; j++){
        if(d[j] > d[i]){
            up[i][0] = j;
            break;
        }
    }
    for(long i = 1; i < K; i++) for(long j = 0; j < n; j++)if(up[j][i - 1] + 1) up[j][i] = up[up[j][i - 1]][i - 1];
    sum.resize(n, vector<long>(K, -1));
    for(long i = 0; i < n; i++) sum[i][0] = c[i];
    for(long i = 1; i < K; i++) for(long j = 0; j < n; j++){
        sum[j][i] = sum[j][i - 1];
        if(up[j][i - 1] >= 0) sum[j][i] += sum[up[j][i - 1]][i - 1];
    }
    long res, v;
    long l, m, r;
    for(long i = 0; i < q; i++){
        cin >> res >> v;
        res--;
        l = 0;
        r = n - 1;
        while(l ^ r){
            m = (l + r) / 2;
            if(f(res, m) < v) l = m + 1;
            else r = m;
        }
        cout << jump(res, l - 1) + 1 << '\n';
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40