Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #pragma GCC optimize("O3")
- #pragma GCC target("avx2")
- using namespace std;
- #define int long long
- #define aint(x) (x).begin(), (x).end()
- typedef long long ll;
- typedef long double ld;
- const int one = 1;
- const int INF = 1e18;
- const int MOD = 1e9 + 7;
- const int N = 2e5;
- const int nul = 0;
- signed main() {
- #ifdef parasha
- freopen("A.in", "r", stdin);
- #endif // parasha
- int n;
- cin >> n;
- vector<int> smth(n);
- for (int &i : smth) cin >> i;
- int pref[n+1] = {0};
- for (int i = 1; i <= n; i++) {
- pref[i] = pref[i-1] + smth[i-1];
- }
- map<int,int> gadost;
- gadost[0] = 1;
- int p = 0;
- int ans = 0;
- for (int i = 1; i <= n; i++) {
- ans += i - max(gadost[pref[i]], p);
- if(gadost[pref[i]]) {
- p = max(p, gadost[pref[i]]);
- }
- if(!smth[i - 1]) {
- p = i;
- }
- gadost[pref[i]] = i+1;
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement