제출 #1250466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250466		Sofiatpc	Fountain (eJOI20_fountain)	C++20	100 / 100	148 ms	9680 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5, MAX = 16, INF = 1e9+5;
int d[MAXN], c[MAXN], nxt[MAX+5][MAXN],  sum[MAXN];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,q; cin>>n>>q;
    for(int i = 1; i <= n; i++)cin>>d[i]>>c[i];

    stack<int> st; st.push(0); 
    d[0] = INF; 

    for(int i = 0; i <= MAX; i++)
        for(int j = 0; j <= n; j++)nxt[i][j] = -1;

    for(int i = n; i >= 1; i--){
        while(d[st.top()] <= d[i])st.pop();

        nxt[0][i] = st.top();
        sum[i] = sum[nxt[0][i]]+c[i];
        st.push(i);
    }

    for(int i = 1; i <= MAX; i++)
        for(int j = 0; j <= n; j++)
            if(nxt[i-1][j] != -1)nxt[i][j] = nxt[i-1][nxt[i-1][j]];

    for(int i = 1; i <= q; i++){
        int r,v; cin>>r>>v;

        int cur = r;
        for(int i = MAX; i >= 0; i--)
            if(nxt[i][cur] != -1 && sum[r] - sum[nxt[i][cur]] < v)
                cur = nxt[i][cur];
        cout<<cur<<"\n";
    }
}

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