Submission #1076441

#TimeUsernameProblemLanguageResultExecution timeMemory
1076441IdanRosenSum Zero (RMI20_sumzero)C++98
22 / 100
114 ms27124 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef std::pair<ll, ll> pii; typedef std::pair<ll, ll> pll; typedef std::pair<ld, ld> pld; #define MAXN 400000 #define LOGN ((ll) log2(MAXN) + 1) ll jump[MAXN][LOGN]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; vector<ll> arr(n); for (auto &i: arr) cin >> i; #define INF LLONG_MAX vector<ll> next(n, INF); { map<ll, set<ll> > sums; vector<ll> pre_sum(n + 1); pre_sum[0] = 0; for (ll i = 0; i < n; i++) { pre_sum[i + 1] = pre_sum[i] + arr[i]; sums[pre_sum[i + 1]].insert(i + 1); } ll curr_sum = 0; for (ll i = 0; i < n; i++) { if (sums.count(curr_sum)) { auto it = sums[curr_sum].upper_bound(i); if (it != sums[curr_sum].end()) next[i] = *it; } curr_sum += arr[i]; } for (ll i = n - 2; i >= 0; i--) next[i] = min(next[i], next[i + 1]); } for (ll i = 0; i < n; i++) jump[i][0] = next[i]; for (ll k = 1; k < LOGN; k++) for (ll i = 0; i < n; i++) jump[i][k] = ((jump[i][k - 1] == INF || jump[i][k - 1] == n) ? INF : jump[jump[i][k - 1]][k - 1]); ll q; cin >> q; while (q-- > 0) { ll l, r; cin >> l >> r; --l; ll ans = 0; ll curr = l; for (ll k = LOGN - 1; k >= 0 && curr < n; k--) { if (jump[curr][k] <= r) { curr = jump[curr][k]; ans += pow(2, k); } } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...