Submission #696136

#	Time	Username	Problem	Language	Result	Execution time	Memory
696136		vjudge1	Fountain (eJOI20_fountain)	C++17	30 / 100	279 ms	30444 KiB

fountain

#include<bits/stdc++.h>
#define INF 1e9+7
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pipii pair<int,pii>
#define plpll pair<ll,pll>
#define vi vector<ll>
#define vvi vector<vi>
#define v3i vector<vvi>
#define v4i vector<v3i>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ins insert
#define ln '\n'
#define all(v) v.begin(),v.end()
using namespace std;

const int up=1e5+5;
int n,Log;
vvi st,vol;
vi C,D,N;

void sparse_table(){
    stack<ll>s;
    s.push(n);
    s.push(n-1);
    N[n-1]=n;
    D[n]=INF;
    ll i=n-2;
    while(i>=0){
        while(s.size()>0&&D[s.top()]<D[i]){
            s.pop();
        }
        if(s.size()!=0){
            N[i]=s.top();
        }
        else{
            N[i]=0;
        }
        s.push(i);
        i--;
    }
    Log=0;
    while((1<<Log)<=n){
        Log++;
    }
    st.resize(Log);
    vol.resize(Log);
    for(ll i=0;i<Log;i++){
        st[i].resize(n+1);
        vol[i].resize(n+1);
    }
    for(ll i=0;i<Log;i++){
        st[i][n]=n;
        vol[i][n]=0;
    }
    N[n]=n;
    C[n]=0;
    for(ll i=0;i<n;i++){
        st[0][i]=N[i];
        //cout<<i<<" "<<N[i]<<ln;
        vol[0][i]=C[i];
    }
    for(ll i=1;i<Log;i++){
        for(ll j=0;j<n;j++){
            st[i][j]=st[i-1][st[i-1][j]];
            //cout<<j<<" "<<i<<" "<<st[i][j]<<ln;
            vol[i][j]=vol[i-1][j]+vol[i-1][st[i-1][j]];
            //cout<<j<<" "<<i<<" "<<vol[i][j]<<ln;
        }
    }
}

ll query(ll w,ll id){
    for(ll i=Log-1;i>=0;i--){
        if(vol[i][id]<w){
            //cout<<id<<" "<<i<<" "<<vol[i][id]<<ln;
            w=w-vol[i][id];
            id=st[i][id];
        }
    }
    id++;
    return id%(n+1);
}

void solve(){
    ll q,id,w;
    cin>>n>>q;
    C.resize(n+1);
    D.resize(n+1);
    N.resize(n+1);
    for(int i=0;i<n;i++){
        cin>>D[i]>>C[i];
    }
    sparse_table();
    while(q--){
        cin>>id>>w;
        id--;
        cout<<query(w,id)<<ln;
    }
}

int main ()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   solve();
}
/*
10 10
0 1 10 100
1 1 5 3
1 7 9 8
0 1 10 9
2 1 2 3
2 9 4
0 1 10 100
1 1 10 2
0 1 10 1000
2 1 5 2
0 1 6
1
0
ll
10
1 2
2 4
4 8
4 9
2 5
1 3
3 6
6 10
3 7
*/

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