Submission #1182972

#TimeUsernameProblemLanguageResultExecution timeMemory
1182972HasanV11010238Sum Zero (RMI20_sumzero)C++20
0 / 100
7 ms576 KiB
#include <bits/stdc++.h> #define ll long long #define INF 10000000 using namespace std; #define LOG 10 #define MAX 400000 int up[MAX][LOG]; int main(){ int n, q, a, l, r, la = 0; ll pr = 0; cin>>n; vector<int> de(n + 1, 0); map<ll, int> ma; ma[0] = 0; for (int i = 1; i <= n; i++){ cin>>a; pr += a; if (ma.find(pr) != ma.end()){ la = max(la, ma[pr]); } up[i][0] = la; de[i] = de[la] + 1; ma[pr] = i; } for (int i = 1; i < LOG; i++){ for (int j = 1; j <= n; j++){ up[j][i] = up[up[up[up[j][i - 1]][i - 1]][i - 1]][i - 1]; } } cin>>q; while (q--){ cin>>l>>r; int st = r; l--; for (int i = 19; i >= 0; i--){ int jmp = up[r][i / 2]; if (i % 2 == 1) jmp = up[jmp][i / 2]; if (jmp >= l){ r = jmp; } } cout<<de[st] - de[r]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...