제출 #1119304

#제출 시각아이디문제언어결과실행 시간메모리
1119304MateiKing80Sum Zero (RMI20_sumzero)C++14
61 / 100
313 ms24876 KiB
#include <bits/stdc++.h> using namespace std; const int N = 4e5; int tata[N + 5], ptr[N + 5]; int a[N + 5], ans[N + 5]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i], a[i] += a[i - 1]; map<int, int> mp; int last = n + 1; mp[a[n]] = n; ans[n + 2] = -1; ans[n + 1] = 0; tata[n + 1] = n + 2; tata[n + 2] = n + 2; for(int i = n; i; i --) { if(mp[a[i - 1]] != 0) last = min(last, mp[a[i - 1]]); mp[a[i - 1]] = i - 1; tata[i] = last + 1; ans[i] = 1 + ans[last + 1]; } int q; cin >> q; for(int i = n + 2; i; i --) { if(ans[ptr[ptr[tata[i]]]] - ans[ptr[tata[i]]] == ans[ptr[tata[i]]] - ans[tata[i]]) ptr[i] = ptr[ptr[tata[i]]]; else ptr[i] = tata[i]; } for(int i = 1; i <= q; i ++) { int l, r, li; cin >> l >> r; li = l; r ++; while(1) { if(ptr[l] <= r) l = ptr[l]; else if(tata[l] <= r) l = tata[l]; else break; } cout << ans[li] - ans[l] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...