Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void solve(){
- const int N = 2e5 + 1;
- int a[N];
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++){
- cin >> a[i];
- }
- long long p[N];
- for (int i = 1; i <= n; i++){
- p[i] = p[i - 1] + a[i];
- }
- map <long long, int> last;
- last[0] = 0;
- int lastI = 0;
- long long ans = 0;
- for (int j = 1; j <= n; j++){
- if (last.count(p[j]) == 0){
- last[p[j]] = j;
- continue;
- }
- int i = last[p[j]] + 1;
- if (i <= lastI){
- continue;
- }
- long long cntL = (i - lastI);
- long long cntR = (n - j + 1);
- ans += cntL * cntR;
- lastI = i;
- last[p[j]] = j;
- }
- cout << ans << endl;
- }
- int main(){
- ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0); // Оптимизация
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement