제출 #855920

#제출 시각아이디문제언어결과실행 시간메모리
855920PetiSum Zero (RMI20_sumzero)C++17
61 / 100
671 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int logn = 19; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; vector<long long> v(n); for(long long &x : v) cin>>x; for(int i = 1; i < n; i++) v[i] += v[i-1]; map<long long, int> mp; vector<vector<int>> nxt(n, vector<int>(logn)); int last = n; for(int i = n-1; i >= 0; i--){ mp[v[i]] = i; long long x = i == 0 ? 0 : v[i-1]; nxt[i][0] = mp.count(x) ? mp[x] : n; if(nxt[i][0] < last){ last = nxt[i][0]; } else{ nxt[i][0] = last; } } for(int j = 1; j < logn; j++){ for(int i = 0; i < n; i++){ nxt[i][j] = nxt[i][j-1] < n-1 ? nxt[nxt[i][j-1]+1][j-1] : n; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; --l, --r; int ans = 0; for(int i = logn-1; i >= 0; i--){ if(l < n && nxt[l][i] <= r) { ans |= 1<<i; l = nxt[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...