Submission #1206858

#TimeUsernameProblemLanguageResultExecution timeMemory
1206858hieptkSum Zero (RMI20_sumzero)C++20
0 / 100
18 ms31808 KiB
#include <iostream> #include <vector> #include <cmath> #include <numeric> #include <algorithm> #include <set> #include <unordered_set> #include <cstring> #include <unordered_map> #include <iomanip> #include <queue> #include <map> #include <sstream> #include <stack> #include <bitset> using ll = long long; using ld = long double; using namespace std; constexpr int nm = 400002; int n, m; ll a[nm], s[nm]; int previ[nm][20]; int getPrev(int i, int j) { for (int u = 0; u < 20 && j && i >= 0; ++u) { if ((j >> u) & 1) { i = previ[i][u]; j &= ~(1 << u); } } return i; } int f(int u, int v) { int l = 1, r = v - u + 1; while (l <= r) { int mid = (l + r) / 2; if (getPrev(v, mid) >= u - 1) { l = mid + 1; } else { r = mid - 1; } } return l - 1; } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); cin >> n; unordered_map<ll, int> seen; seen[0] = 0; memset(previ, -1, sizeof(previ)); for (int i = 1; i <= n; ++i) { cin >> a[i]; s[i] = s[i - 1] + a[i]; previ[i][0] = previ[i - 1][0]; if (seen.count(s[i])) { previ[i][0] = max(seen[s[i]], previ[i][0]); } seen[s[i]] = i; } for (int j = 1; j < 20; ++j) { for (int i = (1 << j); i <= n; ++i) { int u = previ[i][j - 1]; if (u >= 0) previ[i][j] = previ[u][j - 1]; } } cin >> m; int l, r; for (int i = 0; i < m; ++i) { cin >> l >> r; cout << f(l, r) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...