oj.uz

Submission #696128

# Submission time Handle Problem Language Result Execution time Memory
696128 2023-02-05T15:44:09 Z vjudge1 Fountain (eJOI20_fountain) C++17
30 / 100
 171 ms 15200 KB 
#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<int>
#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<int>s;
    s.push(n);
    s.push(n-1);
    N[n-1]=n;
    D[n]=INF;
    int 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(int i=0;i<Log;i++){
        st[i].assign(n+1,0);
        vol[i].assign(n+1,INF);
    }
    for(int i=0;i<Log;i++){
        st[i][n]=n;
        vol[i][n]=0;
    }
    N[n]=0;
    C[n]=0;
    for(int i=0;i<n;i++){
        st[0][i]=N[i];
        //cout<<i<<" "<<N[i]<<ln;
        vol[0][i]=C[i];
    }
    for(int i=1;i<Log;i++){
        for(int 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;
        }
    }
}

int query(int w,int id){
    for(int 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(){
    int 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 15200 KB Output is correct
2 Correct 171 ms 14312 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -