Submission #1201500

#TimeUsernameProblemLanguageResultExecution timeMemory
1201500KK_1729Sum Zero (RMI20_sumzero)C++17
22 / 100
129 ms28288 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); vector<int> suffmin(n+2, 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; } for (int i = n; i >= 1; i--){ suffmin[i] = min(intervals[i], suffmin[i+1]); } int L = 20; vector<vector<int>> rmq(n+5, vector<int>(L, 1e9)); FOR(i,1,n+1){ rmq[i][0] = suffmin[i]; } 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]; } } // cout << "a" <<rmq[5][0] << endl; // cout << rmq[8][0] << endl; 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){ // cout << "a" << l << i << endl; ans += (1 << i); // cout << ans << endl; 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...