제출 #646650

#제출 시각아이디문제언어결과실행 시간메모리
646650VanillaSum Zero (RMI20_sumzero)C++17
61 / 100
518 ms40848 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int64; const int maxn = 4e5 + 5; const int lg = 15; int64 a [maxn]; map <int64, int> ps; int l [maxn]; int jump [maxn][lg]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i <= n + 1; i++){ l[i] = n + 1; } ps[0] = 0; int64 s = 0; for (int i = 1; i <= n; i++){ cin >> a[i]; s+=a[i]; if (ps.count(s)) { l[ps[s] + 1] = i; } ps[s] = i; } for (int i = n; i >= 1; i--){ l[i] = min(l[i], l[i + 1]); jump[i][0] = l[i]; } for (int k = 1; k < lg; k++){ jump[n + 1][k - 1] = n + 1; jump[n + 2][k - 1] = n + 1; for (int i = 1; i <= n; i++){ jump[i][k] = jump[jump[i][k-1] + 1][k-1]; } } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; int rs = 0; for (int i = lg - 1; i >= 0; i--){ while (jump[l][i] <= r) { rs+=(1 << i); l = jump[l][i] + 1; } } cout << rs << "\n"; } // for (auto i: sv){ // cout << i.first << " " << i.second << "\n"; // } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...