Submission #1242015

#TimeUsernameProblemLanguageResultExecution timeMemory
1242015hssaan_arifSum Zero (RMI20_sumzero)C++20
0 / 100
1 ms576 KiB
#include<bits/stdc++.h> using namespace std; #define endl "\n" #define pb push_back #define int long long const int N = 3e5 + 5, M = 1e9 + 7 , LG = 20; int n , a[N] , pr[N] , prv[N] ,last[N] , Q ,L,R , sp[N][LG]; void solve(){ cin >> n; for (int i = 1 ; i <= n ; i++){ cin >> a[i]; } for (int i = 1 ; i <= n ; i++){ pr[i] = pr[i-1] + a[i]; int k = last[pr[i]]; last[pr[i]] = i; prv[i] = max(prv[i-1],k); sp[i][0] = prv[i]; for (int j = 1 ; j < LG ; j++){ sp[i][j] = sp[sp[i][j-1]][j-1]; } } cin >> Q; while(Q--){ cin >> L >> R; int ans = 0; for (int i = LG - 1 ; i >= 0 ; i--){ if (sp[R][i] >= L){ R = sp[R][i]; ans += (1 << i); } } if (sp[R][0] >= L - 1){ ans++; } cout << ans << endl; } // cout << sp[3][0] << endl; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ts = 1; // cin >> ts; while(ts--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...