Submission #1183222

#TimeUsernameProblemLanguageResultExecution timeMemory
1183222HasanV11010238Sum Zero (RMI20_sumzero)C++17
100 / 100
769 ms19824 KiB
#include <bits/stdc++.h> #define ll long long #define INF 10000000 using namespace std; #define LOG 7 #define MAX 400002 int main(){ int n, q, l, r, la; ll pr = 0, a; cin>>n; int up[n + 2][LOG]; la = n + 1; vector<pair<ll, int>> ve(n + 1); ve[0].first = 0, ve[1].second = 0; for (int i = 1; i <= n; i++){ up[i][0] = n + 1; cin>>a; pr += a; ve[i].first = pr, ve[i].second = i; } sort(ve.begin(), ve.end()); for (int i = 1; i <= n; i++){ if (ve[i].first == ve[i - 1].first){ up[ve[i].second][0] = ve[i - 1].second; } } for (int i = 0; i < LOG; i++) up[0][i] = n + 1, up[n + 1][i] = n + 1; for (int i = 1; i <= n; i++){ if (up[i - 1][0] == n + 1) continue; if (up[i][0] == n + 1) up[i][0] = up[i - 1][0]; else up[i][0] = max(up[i][0], up[i - 1][0]); } for (int i = 1; i < LOG; i++){ for (int j = 1; j <= n; j++){ up[j][i] = j; for (int k = 0; k < 8; k++){ up[j][i] = up[up[j][i]][i - 1]; } } } cin>>q; while (q--){ cin>>l>>r; int st = r, ans = 0; l--; for (int i = 19; i >= 0; i--){ int jmp = r; int rep = (1<<(i % 3)); for (int j = 0; j < rep; j++) jmp = up[jmp][i/3]; if (jmp >= l && jmp != n + 1){ r = jmp; ans += (1<<i); } } cout<<ans<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...