oj.uz

Submission #696159

# Submission time Handle Problem Language Result Execution time Memory
696159 2023-02-05T16:31:06 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 360 ms 36668 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<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=18;
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();
        }
        N[i]=s.top();
        s.push(i);
        i--;
    }
    st.resize(Log);
    vol.resize(Log);
    for(int i=0;i<Log;i++){
        st[i].resize(n+1);
        vol[i].assign(n+1,0);
    }
    N[n]=n;
    C[n]=INF;
    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(ll 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 616 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 30460 KB Output is correct
2 Correct 260 ms 28204 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 616 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 237 ms 30460 KB Output is correct
9 Correct 260 ms 28204 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 83 ms 19568 KB Output is correct
12 Correct 360 ms 36668 KB Output is correct
13 Correct 274 ms 35760 KB Output is correct
14 Correct 145 ms 35008 KB Output is correct
15 Correct 124 ms 35312 KB Output is correct