Cod sursa(job #3146632)

Utilizator catalinmarincatalinmarin catalinmarin Data 21 august 2023 22:15:50
Problema Divk Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 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];
long long n, k, a, b;
void two_pointers(vector<long long> v, long long max_length, long long &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;
}