fork download 
  1. //Stay Safe :)
  2.  
  3. #include <bits/stdc++.h>
  4. // video : https://w...content-available-to-author-only...e.com/watch?v=JELQ7dtnChI
  5. using namespace std;
  6. #define lli long long int 
  7.  
  8. int main() {
  9.     lli t;
  10.     cin>>t;
  11.     while(t--){
  12.         lli n;
  13.         cin>>n;
  14.         lli a[n];
  15.         for(lli i=0;i<n;i++){
  16.             cin>>a[i];
  17.             a[i] = a[i]%4;
  18.         }
  19.         lli cnt=0;
  20.         map<lli,pair<lli,lli>> mp;
  21.         // from left hand side
  22.         for(lli i=0;i<n;i++){
  23.             if(a[i]==2 or a[i]==-2){
  24.                 mp[i].first = cnt;
  25.                 cnt=0;
  26.             }
  27.             else{
  28.                 if(a[i]==0)
  29.                     cnt=0;
  30.                 else
  31.                     cnt++;
  32.             }
  33.         }
  34.  
  35.         // again initaialize count zero
  36.         cnt=0;
  37.  
  38.         //from right hand side
  39.         for(lli i=n-1;i>=0;i--){
  40.             if(a[i]==2 or a[i]==-2){
  41.                 mp[i].second = cnt;
  42.                 cnt=0;
  43.             }
  44.             else{
  45.                 if(a[i]==0)
  46.                     cnt=0;
  47.                 else
  48.                     cnt++;
  49.             }
  50.         }
  51.  
  52.         lli invalid=0;
  53.  
  54.         /*
  55.         
  56.         //uncomment if u want to see all x and y 
  57.  
  58.         cout<<"index      x       y"<<endl;
  59.         for(auto xt : mp){
  60.             cout<<xt.first<<"     "<<xt.second.first<<"         "<<xt.second.second<<endl;
  61.         }
  62.         
  63.         //uncomment if u want to see all x+1 and y+1 
  64.         
  65.         cout<<"index      x+1       y+1"<<endl;
  66.         for(auto xt : mp){
  67.             cout<<xt.first<<"     "<<(xt.second.first)+1<<"         "<<(xt.second.second)+1<<endl;
  68.         }
  69.         */
  70.         for(auto xt : mp){
  71.             lli x = xt.second.first;
  72.             lli y = xt.second.second;
  73.             invalid = invalid + (x+1)*(y+1);
  74.         }
  75.         lli total = n*(n+1)/2;
  76.         lli good = total-invalid;
  77.         cout<<good<<endl;
  78.     }
  79. }
Success #stdin #stdout 0s 4344KB
comments ()
stdin 
1
18
34 9 15 5 6 1 1 11 8 5 5 -10 5 15 6 -6 -6 5
stdout 
136
https://ideone.com/f2f4Dx
language:
C++14 (gcc 8.3)
created:
5 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!