제출 #1125987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125987		fgdsa	Fountain (eJOI20_fountain)	C++20	100 / 100	650 ms	31844 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define para pair<ll, ll>

const ll base = 1<<17;
const ll INF = 1e9+7;
const ll LOG = 17;
const ll MAXN = 1e5+7;

ll jump[MAXN][LOG];
ll jumpSum[MAXN][LOG];
ll tree[base<<1];
ll siz[MAXN];
ll d[MAXN];

ll query(ll a, ll b){
    a += base - 1;
    b += base + 1;

    ll res = -INF;
    while(a/2 != b/2){
        if(a % 2 == 0) res = max(res, tree[a+1]);
        if(b % 2 == 1) res = max(res, tree[b-1]);

        a/=2;
        b/=2;
    }

    return res;
}

int main(){ 
    ll n, q;
    cin >> n >> q;

    for(int i = 0; i < 2*base; ++i) tree[i] = INF;
    for(int i = 0; i < n; ++i){
        cin >> d[i] >> siz[i];
        tree[i+base] = d[i];
    }
    for(int i = base-1; i >= 0; --i){
        tree[i] = max(tree[2*i], tree[2*i+1]);
    }

    for(int i = n-1; i >= 0; --i){
        ll pocz = 0, kon = n - 1 - i;
        ll res = -1;
        while(pocz <= kon){
            ll sro = (pocz + kon)/2;
            ll q = query(i, i + sro);
            // cerr << pocz << " " << sro << " " << kon << " " << q << "\n";
            if(q > d[i]){
                kon = sro-1;
                res = sro;
            }
            else{
                pocz = sro+1;
            }
        }

        // cerr << i << ": " << res << '\n';

        if(res == -1){
            jump[i][0] = INF;
            jumpSum[i][0] = INF;
        }else{
            jump[i][0] = res+i;
            jumpSum[i][0] = siz[res+i];
        }
    }

    for(int i = 1; i < LOG; ++i){
        // cerr << i << ":\n";
        for(int j = 0; j < n; ++j){
            // cerr << "   " << j << ": " << jump[j][i-1] << " ";
            if(jump[j][i-1] == INF || jump[jump[j][i-1]][i-1] == INF){ 
                jump[j][i] = INF;
                jumpSum[j][i] = INF;
                continue;
            }
            // cerr << jump[jump[j][i-1]][i-1] << ", " << jumpSum[j][i-1] << '\n';
            jumpSum[j][i] = jumpSum[j][i-1] + jumpSum[jump[j][i-1]][i-1];
            jump[j][i] = jump[jump[j][i-1]][i-1];
        }
    }

    for(int i = 0; i < q; ++i){
        int x, y;
        cin >> x >> y;

        --x;
        ll sum = siz[x];

        for(int j = LOG-1; j >= 0; --j){
            // cerr << j << ": " << x << " " << sum << " " << jump[x][j] << " " << jumpSum[x][j] << " " << y << "\n";
            if(jumpSum[x][j] + sum <= y){
                sum += jumpSum[x][j];
                x = jump[x][j]; 
            }
        }

        if(jump[x][0] != INF && sum < y){
            sum += jumpSum[x][0];
            x = jump[x][0];
        }

        if(sum < y){
            cout << 0 << "\n";
        }
        else{
            cout << x+1 << '\n';
        }
    }

    return 0;
}

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