Cod sursa(job #3151919)

Utilizator KaleemRazaSyedKaleem Raza Syed KaleemRazaSyed Data 23 septembrie 2023 09:21:11
Problema Divk Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<iostream>

using namespace std;

const int N = 500'010;
long long pref[N];
int n, k;

long long find_ans(int b)
{
  int cnt[k] = {0};
  long long ans = 0;

  for(int i = 0; i <= b; ++i)
    ans += cnt[pref[i]], cnt[pref[i]]++;

  for(int i = b; i <= n; i ++)
    cnt[pref[i-b]]-- , ans += cnt[pref[i]]++;
  
  return ans;    
}

int main()
{
  int s, e;
  cin >> n >> k >> s >> e;
  for(int i = 1; i <= n; i ++)
    cin >> pref[i];

  pref[0] = 0;
  for(int i = 0; i < n; i ++)
    pref[i+1] += pref[i];

  for(int i = 0; i <= n; i ++)
    pref[i] %= k;
  
  cout << find_ans(e+1) - find_ans(s) << endl;
  
  return 0;
}