oj.uz

Submission #840851

# Submission time Handle Problem Language Result Execution time Memory
840851 2023-08-31T18:45:14 Z raul2008487 Fountain (eJOI20_fountain) C++17
100 / 100
 563 ms 37616 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define in insert
#define ld long double
#define ll long long
#define pii pair<ll,ll>
#define vl vector<ll>
#define mpr make_pair
#define F first
#define S second
#define lg(a) __lg(a)
#define all(v) v.begin(),v.end()
//#define endl "\n"
#define inf 0x3F3F3F3F
using namespace std;
const int mod = 1e9+7;
const int sz = 1e5+5;
const ll oo = 1000000000000000005;
ll st[20][sz], water[20][sz];
void solve(){
    ll n,q,i,j,len;
    cin>>n>>q;
    deque<pair<ll,ll>> dq;
    for(i=1;i<=n;i++){
        cin>>len>>water[0][i];
        while(!dq.empty() && len > dq.front().first){
            st[0][dq.front().second]=i;
            dq.pop_front();
        }
        dq.push_front({len,i});
    }
    for(i=1;i<20;i++){
        for(j=1;j<=n;j++){
            st[i][j] = st[i-1][st[i-1][j]];
            water[i][j] = water[i-1][j] + water[i-1][st[i-1][j]];
        }
    }
    while(q--){
        ll ix, g;
        cin>>ix>>g;
        for(i=19;i>=0;i--){
            if(water[i][ix] < g){
                g-=water[i][ix];
                ix = st[i][ix];
            }
        }
        cout << ix << endl;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }

}
/*
2 1
1 2 5
4
2
1 2
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Correct 3 ms 852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 30964 KB Output is correct
2 Correct 343 ms 28676 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 330 ms 30964 KB Output is correct
9 Correct 343 ms 28676 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 150 ms 20192 KB Output is correct
12 Correct 563 ms 36712 KB Output is correct
13 Correct 417 ms 36504 KB Output is correct
14 Correct 310 ms 35624 KB Output is correct
15 Correct 304 ms 37616 KB Output is correct