Submission #1201511

#TimeUsernameProblemLanguageResultExecution timeMemory
1201511KK_1729Sum Zero (RMI20_sumzero)C++20
61 / 100
478 ms53512 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define pb push_back #define all(a) a.begin(), a.end() #define endl "\n" void printVector(vector<int> a){ for (auto x: a) cout << x << " "; cout << endl; } void solve(){ int n; cin >> n; vector<int> a(n+1); FOR(i,1,n+1) cin >> a[i]; vector<int> prefix(n+1); FOR(i,1,n+1) prefix[i] = prefix[i-1]+a[i]; // printVector(prefix); map<int, vector<int>> o; FOR(i,1,n+1){ o[prefix[i]].pb(i); } vector<int> intervals(n+1, 1e9); FOR(i,1,n+1){ auto ind = lower_bound(all(o[prefix[i-1]]), i); if (ind == o[prefix[i-1]].end()) continue; intervals[i] = *ind; } prefix.clear(); a.clear(); o.clear(); int L = 18; int rmq[n+5][18]; FOR(i,0,n+5){ FOR(j,0,18) rmq[i][j] = 10000000; } for (int i = n; i >= 1; i--){ // suffmin[i] = min(intervals[i], suffmin[i+1]); rmq[i][0] = min(intervals[i], rmq[i+1][0]); } for (int j = 1; j < L; j++){ for (int i = 1; i <= n; i++){ if (rmq[i][j-1] <= n) rmq[i][j] = rmq[ rmq[i][j-1]+1 ][j-1]; } } int q; cin >> q; while (q--){ int l, r; cin >> l >> r; int ans = 0; for (int i = L-1; i >= 0; i--){ // cout << l << endl; if (l > n) break; if (rmq[l][i] <= r){ ans += (1 << i); l = rmq[l][i]+1; } } cout << ans << endl; } } int32_t main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int t = 1;// cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...