fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	int t,n1,k;
  6. 	cin>>t;
  7. 	while(t--){
  8.     cin>>n1>>k;
  9.     int A[n1];
  10.     for(int i = 0 ; i<n1 ; i++){
  11.         cin>>A[i];
  12.     }
  13.     int presum[n1+1];
  14.     for(int i = 0 ; i<n1+1 ; i++){
  15.         presum[i] = 0;
  16.     }
  17.     map<int,int>map1,map2;
  18.     for(int i = 1 ; i<=n1 ; i++){
  19.         presum[i] = presum[i-1]+A[i-1];
  20.     }
  21.     for(int i = 0 ; i<=n1 ; i++){
  22.         if(map1.find(presum[i])==map1.end()){
  23.             map1[presum[i]] = i;
  24.         }
  25.         map2[presum[i]] = i;
  26.     }
  27.     int maxi = 0,mini=INT_MAX;
  28.     for(int i = 1 ; i<=n1 ; i++){
  29.         if(map1.find(presum[i]-k)!=map1.end()){
  30.             maxi = max(maxi,abs(i-map1[presum[i]-k]));
  31.         }
  32.         if(map2.find(presum[i]-k)!=map2.end()){
  33.             mini = min(mini,abs(i-map2[presum[i]-k]));
  34.         }
  35.     }
  36.     int cnt1 = 0,cnt2=0;
  37.     for(int i = 1 ; i<=n1 ; i++){
  38.         if(map1.find(presum[i]-k)!=map1.end()){
  39.             if(maxi==(i-map1[presum[i]-k])){
  40.                 cnt1++;
  41.             }
  42.         }
  43.         if(map2.find(presum[i]-k)!=map2.end()){
  44.             if(mini==(i-map2[presum[i]-k])){
  45.                 cnt2++;
  46.             }
  47.         }
  48.     }
  49.     cout<<cnt2<<" "<<cnt1<<endl;//cnt2 --> shortest subarrays count cnt1 --> longest subarrays count
  50. 	}
  51. 	return 0;
  52. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
3
6 15
10 5 2 7 1 -10
6 -5
-5 8 -14 2 4 12
5 4
3 1 3 -2 2
stdout
copy 
1 1
1 1
2 1
https://ideone.com/5KBpiV
language:
C++14 (gcc 8.3)
created:
4 days 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!