oj.uz

답안 #1120027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1120027 2024-11-27T18:29:59 Z boris_7 Fountain (eJOI20_fountain) C++17
100 / 100
 705 ms 45476 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<ll>>gp;


void solve() {
    ll n,q;
    cin>>n>>q;
    gp = vector<vector<ll>>(n);
    vector<ll>d(n+1),c(n+1);
    d.back()=1e15;
    c.back()=1e15;
    for(ll i = 0;i<n;i++){
        cin>>d[i]>>c[i];
    }
    stack<ll>st;
    st.push(n);
    vector<vector<pair<ll,ll>>>up(n+1,vector<pair<ll,ll>>(20,{n,0}));
    for(ll i = n-1;i>=0;i--){
        while(st.size() && d[st.top()]<=d[i]){
            st.pop();
        }
        up[i][0]={st.top(),c[i]};
        st.push(i);
    }
    for(ll i = 1;i<20;i++){
        for(ll j = 0;j<n;j++){
            ll ne = up[j][i-1].first;
            up[j][i]={up[ne][i-1].first,up[j][i-1].second+up[ne][i-1].second};
        }
    }
    while(q--){
        ll ind,val;
        cin>>ind>>val;
        --ind;
        // cout<<i<<" "<<ind<<" "<<val<<endl;
        // cout<<up[ind][1].second<<endl;
        for(ll i = 19;i>=0;--i){
            if(up[ind][i].second<val){
                val-=up[ind][i].second;
                ind =up[ind][i].first;
            }
        }
        if(ind == n) cout<<0<<endl;
        else cout<<ind+1<<endl;
    }
    
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // ll t;cin>>t;while(t--)
        solve();
}
/*
5
0
5
4
2
*/

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 399 ms 42092 KB Output is correct
2 Correct 502 ms 39244 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 399 ms 42092 KB Output is correct
9 Correct 502 ms 39244 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 231 ms 24296 KB Output is correct
12 Correct 705 ms 45476 KB Output is correct
13 Correct 548 ms 44364 KB Output is correct
14 Correct 440 ms 43596 KB Output is correct
15 Correct 400 ms 43860 KB Output is correct