oj.uz

답안 #912507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912507 2024-01-19T14:46:56 Z andro Fountain (eJOI20_fountain) C++14
100 / 100
 921 ms 25936 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 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 5 ms 4440 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 5 ms 4440 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 514 ms 24240 KB Output is correct
2 Correct 722 ms 24440 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 5 ms 4440 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 5 ms 4440 KB Output is correct
8 Correct 514 ms 24240 KB Output is correct
9 Correct 722 ms 24440 KB Output is correct
10 Correct 8 ms 4696 KB Output is correct
11 Correct 311 ms 17748 KB Output is correct
12 Correct 875 ms 25936 KB Output is correct
13 Correct 921 ms 25156 KB Output is correct
14 Correct 660 ms 23900 KB Output is correct
15 Correct 517 ms 24200 KB Output is correct