Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #pragma GCC optimize("O3")
  4. #pragma GCC target("avx2")
  5.  
  6. using namespace std;
  7.  
  8. #define int long long
  9. #define aint(x) (x).begin(), (x).end()
  10. typedef long long ll;
  11. typedef long double ld;
  12.  
  13. const int one = 1;
  14. const int INF = 1e18;
  15. const int MOD = 1e9 + 7;
  16. const int N = 2e5;
  17. const int nul = 0;
  18.  
  19. signed main() {
  20. #ifdef parasha
  21.     freopen("A.in", "r", stdin);
  22. #endif // parasha
  23.     int n;
  24.     cin >> n;
  25.     vector<int> smth(n);
  26.     for (int &i : smth) cin >> i;
  27.     int pref[n+1] = {0};
  28.     for (int i = 1; i <= n; i++) {
  29.         pref[i] = pref[i-1] + smth[i-1];
  30.     }
  31.     map<int,int> gadost;
  32.     gadost[0] = 1;
  33.     int p = 0;
  34.     int ans = 0;
  35.     for (int i = 1; i <= n; i++) {
  36.  
  37.         ans += i - max(gadost[pref[i]], p);
  38.  
  39.         if(gadost[pref[i]]) {
  40.             p = max(p, gadost[pref[i]]);
  41.         }
  42.         if(!smth[i - 1]) {
  43.             p = i;
  44.         }
  45.         gadost[pref[i]] = i+1;
  46.     }
  47.     cout << ans << endl;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement