oj.uz

Submission #446103

# Submission time Handle Problem Language Result Execution time Memory
446103 2021-07-20T22:47:28 Z Ronin13 Fountain (eJOI20_fountain) C++14
100 / 100
 309 ms 24656 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define epb emplace_back
#define pb push_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

void solve(){
    int n;cin>>n;
    int q;cin>>q;
    int  c[n+2],d[n+2];
    for(int i=1;i<=n;i++){
        cin>>d[i]>>c[i];
    }
    stack<int>st;
    st.push(n+1);
    d[n+1]=2*inf+1;
    int next[n+2][22];
    int water[n+2][22];
    next[n+1][0]=n+1;
    int par[n+2];
    for(int i=1;i<=n+1;i++){
        par[i]=0;
    }
    int pref[n+2];
    pref[0]=0;
    pref[n+1]=2*inf;

    for(int i=n;i>=1;i--){
        while(true){
            int ind=st.top();
            if(d[ind]>d[i]){
                next[i][0]=ind;
                water[i][0]=c[i];
                par[ind]=i;
                break;
            }
            else st.pop();
        }
        st.push(i);
    }
    for(int j=1;j<=21;j++){
        for(int i=1;i<=n+1;i++){
            next[i][j]=next[next[i][j-1]][j-1];
            water[i][j]=water[i][j-1]+water[next[i][j-1]][j-1];
        }
    }


    while(q--){
        int ves;int l;
        cin>>ves>>l;

        for(int i=21;i>=0;i--){
            int nex=next[ves][i];
            if(l>water[ves][i])l-=water[ves][i],ves=nex;
        }
        cout<<ves%(n+1)<<"\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
}

Compilation message

fountain.cpp: In function 'void solve()':
fountain.cpp:27:9: warning: variable 'par' set but not used [-Wunused-but-set-variable]
   27 |     int par[n+2];
      |         ^~~
fountain.cpp:31:9: warning: variable 'pref' set but not used [-Wunused-but-set-variable]
   31 |     int pref[n+2];
      |         ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 448 KB Output is correct
7 Correct 1 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 19268 KB Output is correct
2 Correct 226 ms 17844 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 448 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 209 ms 19268 KB Output is correct
9 Correct 226 ms 17844 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 92 ms 12996 KB Output is correct
12 Correct 309 ms 24656 KB Output is correct
13 Correct 221 ms 23876 KB Output is correct
14 Correct 183 ms 23136 KB Output is correct
15 Correct 159 ms 23492 KB Output is correct