fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long sl;
  5. vector <ll> a;
  6. int mex_subarray( int l, int r) {
  7.     set<int> s;
  8.     for (int i = l-1; i <r ;i++)
  9.         s.insert(a[i]);
  10.  
  11.     int m = 0;
  12.     while (s.count(m))
  13.         m++;
  14.     return m;
  15. }
  16. void solve(){
  17.    int n ;cin >> n ;
  18.     a.resize(n);
  19.     vector <ll >presum(n+1) ;
  20.     map <ll ,int> idx , cnt;
  21.     idx[0] =0 ;
  22.     for (int i=0 ; i <n ;i++) {
  23.         cin >> a[i] ;
  24.         presum[i+1] = presum[i] + a[i] ;
  25.         cnt[presum[i+1]]++ ;
  26.         if (idx.find(presum[i+1]) == idx.end()) idx[presum[i+1]] = i+1;
  27.     }
  28.     int ans = 0 ;
  29.     for (int i=1; i <=n ;i++) {
  30.         ll search3 = presum[i]- 3 , search2 = presum[i]-2;
  31.         if (idx.find(search3) != idx.end() && idx[search3] < i)  {
  32.             int me_x= mex_subarray(idx[search3] +1, i) ;
  33.             if (me_x == 3) {
  34.                 ans+=cnt[search3];
  35.             }
  36.         }
  37.         if (idx.find(search2) != idx.end() && idx[search2] < i) {
  38.             int me_x= mex_subarray( idx[search2]+1 ,i) ;
  39.             if (me_x == 2) {
  40.                 ans+=cnt[search2];
  41.             }
  42.         }
  43.     }
  44.     cout << ans << endl ;
  45. }
  46.  
  47.  
  48.  
  49. signed main() {
  50.     ios::sync_with_stdio(0);cin.tie(0);
  51.    //int t ; cin >> t; while(t--)
  52.         solve();
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/jpX0bL
language:
C++ (gcc 8.3)
created:
1 day 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!