Submission #549272

#TimeUsernameProblemLanguageResultExecution timeMemory
549272kevinxiehkSum Zero (RMI20_sumzero)C++17
22 / 100
132 ms26648 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb emplace_back #define fi first #define se second #define int long long #define inf 1e18 #define ick cout<<"ickbmi32.9\n" using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; int arr[n + 5]; int ps[n + 5]; int next[n + 5]; map<int, int> la; ps[0] = 0; for(int i = 1; i <= n; i++) { cin >> arr[i]; ps[i] = ps[i - 1] + arr[i]; next[i] = n + 1; if(la[ps[i]] != 0 || ps[i] == 0) { next[la[ps[i]] + 1] = min(next[la[ps[i]] + 1], i); } la[ps[i]] = i; } for(int i = n - 1; i >= 1; i--) { next[i] = min(next[i], next[i + 1]); } // for(int i = 1; i <= n; i++) { // cout << next[i] << ' '; // }cout << '\n'; //return 0; int sps[n + 5][25]; next[n + 1] = n + 1; next[n + 2] = n + 1; for(int i = 1; i <= n + 2; i++) { sps[i][0] = next[i]; } for(int j = 1; j < 20; j++) { for(int i = 1; i <= n + 2; i++) { sps[i][j] = sps[sps[i][j - 1] + 1][j - 1]; if(sps[i][j] > n) sps[i][j] = n + 1; // cout << sps[i][j] << ' '; } // cout << '\n'; }//return 0; int q; cin >> q; while(q--) { int l, r; cin >> l >> r; int ans = 0; for(int i = 19; i >= 0; i--) { if(sps[l][i] <= r) { ans += (1 << i); l = sps[l][i] + 1; } } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...