# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1243382 | asdfghqwert | Sum Zero (RMI20_sumzero) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops,fast-math")
//#pragma GCC optimize("O3,Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
int n ;cin >> n;
const int lg = 14;
const int N = n + 10;
int dp[N][lg], lst = 1 , val = 0;
memset(dp , 0 , sizeof(dp));
map<int , int> mp;mp[0] = 0;
for(int i = 1 ; i <= n ; i++){
int tl;cin >> tl
cin >> tl;
val += tl;
if(mp.count(val)){
int k = mp[val];
for(int j = lst ; j <= k + 1; j++){
dp[j][0] = i;
}
lst = max(k + 2 , lst);
}
mp[val] = i;
}
// for(int i = 1 ; i <= n ; i++)cout << dp[i][0] << ' ';
for(int i = 1 ; i < lg ; i++){
for(int j = 1 ; j <= n ; j++){
if(dp[j][i - 1] == 0)break;
dp[j][i] = dp[dp[j][i - 1] + 1][i - 1];
}
}
int q; cin >> q;
while(q--){
int cur ,r , ans = 0;
cin >> cur >> r;
for(int j = lg - 1 ; j >= 0 ; j--){
if(cur > r)break;
if(dp[cur][j] <= r && dp[cur][j] > 0){
ans += (1 << j);
cur = dp[cur][j] + 1;
}
}
cout << ans << '\n';
}
}