Advertisement
miglss

5

Mar 21st, 2023
26
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. void solve(){
  6. const int N = 2e5 + 1;
  7. int a[N];
  8. int n;
  9. cin >> n;
  10. for (int i = 1; i <= n; i++){
  11. cin >> a[i];
  12. }
  13. long long p[N];
  14. for (int i = 1; i <= n; i++){
  15. p[i] = p[i - 1] + a[i];
  16. }
  17. map <long long, int> last;
  18. last[0] = 0;
  19. int lastI = 0;
  20. long long ans = 0;
  21. for (int j = 1; j <= n; j++){
  22. if (last.count(p[j]) == 0){
  23. last[p[j]] = j;
  24. continue;
  25. }
  26. int i = last[p[j]] + 1;
  27. if (i <= lastI){
  28. continue;
  29. }
  30. long long cntL = (i - lastI);
  31. long long cntR = (n - j + 1);
  32. ans += cntL * cntR;
  33. lastI = i;
  34. last[p[j]] = j;
  35. }
  36. cout << ans << endl;
  37.  
  38. }
  39.  
  40. int main(){
  41. ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0); // Оптимизация
  42. solve();
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement