Cod sursa(job #2662710)

Utilizator Rares31100Popa Rares Rares31100 Data 24 octombrie 2020 12:52:37
Problema Divk Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("divk.in");
ofstream out("divk.out");
int n, k, a, b, val[500001], r[100001];

long long siruri(int lung)
{
    if(lung == 0)
        return 0;
    
    long long rez = 0;
    int suma = 0, pas = 0;
    
    for(int i = 0; i < k; i++)
        r[i] = 0;
    
    for(int i = 1; i <= n; i++)
    {
        if(i > lung)
        {
            r[(pas+suma)%k]--;
            suma = (suma + val[i] - val[i-lung]%k + k) % k;
        }
        else
            suma = (suma + val[i]) % k;
            
        pas = (pas - val[i]%k + k) % k;
        r[(pas+val[i])%k]++;
        rez += r[pas];
    }
    
    return rez;
}

int main()
{
    in >> n >> k >> a >> b;
    
    for(int i = 1; i <= n; i++)
        in >> val[i];
       
    out << siruri(b) - siruri(a-1);
    return 0;
}