fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
  3. #pragma GCC optimize("unroll-loops")
  4. /***
  5. **     Author: Rois Uddin Khan Emon
  6. **     Bangladesh University of Business and Technology
  7. **     Dept. of CSE.
  8. ***    version: 0.0
  9. ***/
  10.  
  11. #include <stdio.h>
  12. #include <iostream>
  13. #include <sstream>
  14. #include <string.h>
  15. #include <string>
  16. #include <cwctype>
  17. #include <math.h>
  18. #include <vector>
  19. #include <iterator>
  20. #include <map>
  21. #include <set>
  22. #include <stack>
  23. #include <algorithm>
  24.  
  25. #define pb push_back
  26. #define Sqr(n) (n * n)
  27. #define Sort(v) sort(v.begin(), v.end())
  28. #define Mxe(v) *max_element(v.begin(), v.end())
  29. #define Mne(v) *min_element(v.begin(), v.end())
  30. #define Fin freopen("input.txt","r", stdin)
  31. #define Fout freopen("output.txt","w", stdout)
  32.  
  33. using namespace std;
  34.  
  35. typedef long long ll;
  36. typedef long long int lli;
  37. typedef unsigned long long ull;
  38. const double PI = acos(-1.0);
  39. const lli maxn = 1e5+7;
  40.  
  41. template <typename T> T Abs(T a) { if (a < 0) return -a; else return a; }
  42. template <typename T> T BigMod(T b, T p, T m) { if (p == 0) return 1; if (p % 2 == 0) { T s = BigMod(b, p / 2, m); return ((s % m) * (s % m)) % m; } return ((b % m) * (BigMod(b, p - 1, m) % m)) % m; }
  43. template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
  44. template <typename T> T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
  45. template <typename T> T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
  46.  
  47. char uplowch(char ch){if(ch >= 'A' &&  ch <= 'Z') ch += 32; return ch;}
  48. char lowupch(char ch){if(ch >= 'a' &&  ch <= 'z') ch -= 32; return ch;}
  49. string intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}
  50.  
  51. #define MOD 1000000007
  52. #define MAX -1000000007
  53. #define MIN 1000000007
  54.  
  55. int binarySearch(lli a[], int left , int right, lli x){
  56.     int count = 0;
  57.     int mid = 0;
  58.     while(left<=right){
  59.         mid = (left + right)/2;
  60.         if(a[mid]>x){
  61.             right = mid-1;
  62.         }else if(a[mid]<x){
  63.             left = mid+1;
  64.         }else{
  65.             count++;
  66.             break;
  67.         }
  68.     }
  69.  
  70.     return count;
  71. }
  72. int countSubarraySum( lli a[], int size, lli x){
  73.     int count = 0;
  74.     int idx = upper_bound(a, a+size, x)-a;
  75.     for(int i = idx; i<size; i++){
  76.         count += binarySearch(a, 0, i-1,  a[i]-x);
  77.     }
  78.     return count;
  79. }
  80.  
  81. int main(){
  82.     int n;
  83.     lli x;
  84.     cin>>n>>x;
  85.     lli arr[n];
  86.     for(int i = 0; i<n; i++){
  87.         lli val;
  88.         cin>>val;
  89.         i!=0 ? arr[i] = arr[i-1]+val: arr[i] = val;
  90.     }
  91.     cout<<binarySearch(arr, 0, n-1, x) + countSubarraySum(arr, n, x)<<endl;
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5 7
2 4 1 2 7
stdout
copy 
3
https://ideone.com/xyBfyp
language:
C++14 (gcc 8.3)
created:
6 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!