fork download
copy 
  1. // R SAI KRISHNA 
  2. #include<iostream>
  3. #include<vector>
  4. #include<string>
  5. #include<algorithm>
  6. #include<stack>
  7. #include<unordered_set>
  8. #include<cmath>
  9. #include<numeric>
  10. #include<iterator>
  11. #include<set>
  12. #include<unordered_map>
  13. #include<map>
  14. #include<queue>
  15. #include<cstring>
  16. #include<stdio.h>
  17. #include<fstream>
  18. #include<iomanip>
  19. #include<functional>
  20. #include<bitset>
  21. #include<chrono>
  22. #include<climits>
  23. #include<assert.h>
  24. #include<random>
  25. #include<complex>
  26. // #include<ext/pb_ds/assoc_container.hpp>
  27. // #include<ext/pb_ds/tree_policy.hpp>
  28. #define for0(i, n) for (int i = 0; i < (ll)(n); ++i)
  29. #define for1(i, n) for (int i = 1; i <= (ll)(n); ++i)
  30. #define forc(i, l, r) for (int i = (ll)(l); i <= (ll)(r); ++i)
  31. #define forr0(i, n) for (int i = (ll)(n) - 1; i >= 0; --i)
  32. #define forr1(i, n) for (int i = (ll)(n); i >= 1; --i)
  33. #define pb push_back
  34. #define fi first  
  35. #define debug(x) cout << #x << " -> " << x << endl;
  36. #define endl '\n'
  37. #define se second
  38. #define all(x) (x).begin(), (x).end()
  39. #define rall(x) (x).rbegin, (x).rend()
  40. #define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)
  41. #define present(c,x) ((c).find(x) != (c).end())
  42. #define cpresent(c,x) (find(all(c),x) != (c).end())
  43. #define sz(a) ll((a).size())
  44. #define mod 1000000007
  45. #define INF LLONG_MAX
  46. using namespace std;
  47. //using namespace __gnu_pbds;
  48. typedef vector<int> vi;
  49. typedef vector<vi> vvi;
  50. typedef pair<int, int> ii;
  51. typedef vector<ii> vii;
  52. typedef long long ll;
  53. typedef vector<ll> vll;
  54. typedef vector<vll> vvll;
  55. typedef double ld; 
  56. //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  57. void debug_vec(vector<ll>&v){  
  58.     cout << '[';
  59.     for(auto i:v)cout << i << ", "; cout << "]";
  60.     cout << "\n";
  61. }   
  62.  
  63. void debug_set(set<ll>&st){  
  64.     cout << "{";
  65.     for(auto i:st)cout << i << ", ";
  66.     cout << "}";
  67.     cout << "\n";
  68. } 
  69.  
  70.  
  71. void fast()
  72. {
  73.   ios_base::sync_with_stdio(0);
  74.   cin.tie(0);
  75.   cout.tie(0);
  76. } 
  77.  
  78. bool prime[1000001];
  79. void sieve()
  80. {
  81.   memset(prime, true, sizeof(prime));
  82.   prime[1]=false;
  83.   for (int p=2; p*p<=1000000; p++)
  84.   {
  85.     if (prime[p] == true)
  86.     {
  87.         for (int i=p*p; i<=1000000; i += p)
  88.                 prime[i] = false;
  89.     }
  90.   }
  91. } 
  92.  
  93. void print(bool f){ 
  94.     if(f)cout << "YES\n"; 
  95.     else cout << "NO\n";
  96. }  
  97.  
  98. void google(int x){  
  99.     cout << "Case #" << x << ": " ;
  100. }  
  101.  
  102. ll binary_expo(ll a,ll b){ 
  103.     ll res = 1; 
  104.     while(b != 0){ 
  105.         if(b&1){ 
  106.             res = (res * a) % mod; 
  107.  
  108.         } 
  109.         b >>= 1; 
  110.         a = (a*a)%mod;
  111.     } 
  112.     return res;
  113. } 
  114.  
  115. void solve()
  116. {
  117.     ll n; 
  118.     cin >> n; 
  119.     ll a[n];  
  120.     ll total = 0;
  121.     for(int i=0;i<n;i++){ 
  122.         cin >> a[i]; 
  123.         total += (a[i] != 0)?1:0;
  124.     } 
  125.     vector<pair<ll,ll>>v; 
  126.     map<ll,vll>mp;  
  127.     ll start = 0; 
  128.     mp[0ll].pb(0ll); 
  129.     ll pre[n]; 
  130.     for(int i=0;i<n;i++){ 
  131.         pre[i] = a[i]; 
  132.         if(i >= 1)pre[i] += pre[i-1];
  133.     } 
  134.     bool f = false;
  135.     for(int i=0;i<n;i++){  
  136.         if(sz(mp[pre[i]]) == 1){ 
  137.             f = true; 
  138.             ll start_seg = *mp[pre[i]].begin(); 
  139.             ll end_seg = i + 1; 
  140.             total += max(((end_seg - start_seg)*(end_seg - start_seg - 1))/2 - 1,0ll); 
  141.             total += max(0ll,((start_seg - start)*(start_seg - start - 1))/2); 
  142.             start = *mp[pre[i]].begin() + 1; 
  143.             ll res = *mp[pre[i]].begin() + 1; 
  144.             v.pb({res,end_seg});
  145.             mp.clear(); 
  146.             if(res <= n)
  147.             mp[pre[res - 1]].pb(res);
  148.         }  
  149.         else { 
  150.             mp[pre[i]].pb(i + 1);
  151.         }
  152.     }    
  153.  
  154.     if(start <= n)
  155.     total += max(0ll,((n - start)*(n - start - 1))/2); 
  156.     for(auto i : v){  
  157.     total -= max(0ll,((i.second - i.first)*(i.second - i.first - 1))/2);
  158. }
  159.     cout << total << endl;
  160. } 
  161.  
  162. int main()
  163. {
  164.   fast();
  165.   /*ll t;
  166.   cin >> t;
  167.   for(int tt = 1;tt <= t ;tt++)*/
  168.   solve();
  169.  
  170. return 0;
  171. }
  172.  
Success #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
3 
41 -41 41
stdout
copy 
3
https://ideone.com/kLEfQ1
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!