oj.uz

답안 #843208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843208 2023-09-03T19:25:14 Z Andrijanikolic73 Fountain (eJOI20_fountain) C++17
100 / 100
 734 ms 25956 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int n;
int q;
int koliko[N];
int staje[N];
int up[N][21];
int suf[N];
stack<int>s;
int P[N];
int kti(int n,int k){
    for(int i=0;i<=20;i++){
        if(k&(1ll<<i))n=up[n][i];
    }
    return n;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>koliko[i]>>staje[i];
    for(int i=0;i<=n;i++)P[i]=0;
    for(int i=n;i>=1;i--){
        while(s.size()&&koliko[s.top()]<=koliko[i])s.pop();
        if(s.size())P[i]=s.top();
        s.push(i);
    }
    for(int i=0;i<=n;i++)suf[i]=0;
    for(int i=1;i<=n;i++)if(!P[i])suf[i]=staje[i];
    for(int i=n;i>=1;i--){
        if(P[i])suf[i]=suf[P[i]]+staje[i];
    }
    for(int i=0;i<=n;i++)for(int j=0;j<=20;j++)up[i][j]=0;
    for(int i=1;i<=n;i++){
        up[i][0]=P[i];

    }
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            up[j][i]=up[up[j][i-1]][i-1];
        }
    }
    while(q--){
        int q,k;
        cin>>q>>k;
        if(suf[q]<k){
            cout<<0;
            cout<<endl;
            continue;
        }
        int l=0,r=n;int R=-1;
        while(l<=r){
            int mid=(l+r)/2;
            int X=kti(q,mid);
            int y=P[X];
            if(suf[q]-suf[y]<k)l=mid+1;
            else {
                r=mid-1;
                R=mid;
            }
        }
        cout<<kti(q,R);
        cout<<endl;
    }
}
/*
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
*/

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 3 ms 4592 KB Output is correct
5 Correct 5 ms 4440 KB Output is correct
6 Correct 5 ms 4580 KB Output is correct
7 Correct 4 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 488 ms 21232 KB Output is correct
2 Correct 553 ms 24680 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 3 ms 4592 KB Output is correct
5 Correct 5 ms 4440 KB Output is correct
6 Correct 5 ms 4580 KB Output is correct
7 Correct 4 ms 4444 KB Output is correct
8 Correct 488 ms 21232 KB Output is correct
9 Correct 553 ms 24680 KB Output is correct
10 Correct 4 ms 4444 KB Output is correct
11 Correct 279 ms 17740 KB Output is correct
12 Correct 734 ms 25956 KB Output is correct
13 Correct 667 ms 24892 KB Output is correct
14 Correct 483 ms 24060 KB Output is correct
15 Correct 463 ms 24304 KB Output is correct