Cod sursa(job #3146631)

Utilizator catalinmarincatalinmarin catalinmarin Data 21 august 2023 22:15:18
Problema Divk Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("divk.in");
ofstream cout("divk.out");
vector<long long> v[100001];
long long numere[500001];
long long sp[500001];
int n, k, a, b;
void two_pointers(vector<long long> v, int max_length, int &max_answer){
    int left = 0;
    for (int right = 0; right < (int) v.size(); right++){
        while (v[right] - v[left] > max_length){
            left++;
        }
        max_answer += (right - left);
    }
}
int main(){
    long long raspuns_maxim_b = 0;
    long long raspuns_maxim_a = 0;
    cin >> n >> k >> a >> b;
    v[0].push_back(0);
    for (int i = 1; i <= n; i++){
        cin >> numere[i];
        sp[i] = (sp[i - 1] + numere[i]) % k;
        v[sp[i]].push_back(i);
    }
    for (int i = 0; i < k; i++){
        two_pointers(v[i], b, raspuns_maxim_b);
        two_pointers(v[i], a - 1, raspuns_maxim_a);
    }
    cout << raspuns_maxim_b - raspuns_maxim_a;
}