fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(0);cin.tie(0);
  4. #define ll long long
  5. const int maxn = 2e5+5;
  6. ll n,M;
  7. ll a[maxn];
  8. struct Bit{
  9.     ll s;
  10.     vector<ll> bit;
  11.     Bit(ll n){
  12.         s = n;
  13.         bit.assign(s+1,0);
  14.     }
  15.     void add(ll idx, ll val){
  16.         while(idx<=s){
  17.             bit[idx]+=val;
  18.             idx+= idx&(-idx);
  19.         }
  20.     }
  21.     ll get(ll idx){
  22.         ll sum = 0;
  23.         while(idx>0){
  24.             sum+=bit[idx];
  25.             idx-=idx&(-idx);
  26.         }
  27.         return sum;
  28.     }
  29.     ll query(ll l, ll r){
  30.         return get(r) - get(l-1);
  31.     }
  32. };
  33.  
  34. void solve(){
  35.     cin >> n >> M;
  36.     for(int i = 0;i<n;i++){
  37.         cin >> a[i];
  38.     }
  39.     ll d[n+5];
  40.     ll prec = 0;
  41.     ll prel = 0;
  42.     d[0] = 0;
  43.     for(int i = 1;i<=n;i++){
  44.         if(a[i-1]%2==0){
  45.             prec+=a[i-1];
  46.         }
  47.         else{
  48.             prel+=a[i-1];
  49.         }
  50.         d[i] = prec - prel;
  51.     }
  52.     // d[r] - M <= d[l-1] <= d[r];
  53.     vector<ll> dl;
  54.     for(int i = 0;i<=n;i++){
  55.         dl.push_back(d[i]);
  56.         dl.push_back(d[i]-M);
  57.     }
  58.     vector<ll> comp = dl;
  59.     sort(comp.begin(),comp.end());
  60.     map<ll,int> mp;
  61.     int idx = 1;
  62.     for(ll i : comp){
  63.         if(mp.find(i) == mp.end()){
  64.             mp[i] = idx;
  65.             idx++;
  66.         }
  67.     }
  68.  
  69.     Bit bit(comp.size()+1);
  70.     int odd = 0;
  71.     int even = 0;
  72.     int p = 0;
  73.     ll ans = 0;
  74.     for(int i = 0;i<n;i++){
  75.         if(a[i]%2==0){
  76.             even = i+1;
  77.         }
  78.         else{
  79.             odd = i+1;
  80.         }
  81.         int k = min(even,odd);
  82.         while(p<=k-1){
  83.             bit.add(mp[d[p]],1);
  84.             p++;
  85.         }
  86.         ans+=bit.query(mp[d[i+1]-M], mp[d[i+1]]);
  87.     }
  88.     cout << ans;
  89. }
  90. int main(){
  91.     freopen("CHANLE.INP","r",stdin);
  92.     freopen("CHANLE.OUT","w",stdout);
  93.     fast;
  94.     solve();
  95. }
  96.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/huL6kd
language:
C++14 (gcc 8.3)
created:
5 hours 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!