Do not gather!

Link: https://training.olinfo.it/task/ois_gatherings
Fonte: OIS 2021 round 3

Categoria

sliding window

Problema facile non ovvio

Hint 1:

Sliding window

Sketch di soluzione:

Sliding window, l è l'elemento per cui calcolo il numero di elementi più vicini di D, r è l'elemento più lontano con P[r]-P[l] <= D;

Soluzione:

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, d; cin >> n >> d;
  vector<int> p(n); for(int i = 0; i<n; i++) cin >> p[i];
  int l = 0; int r = 0;
  long long sol = 0;
  for(int l = 0; l<n-1; l++){
    while(r < n && p[r]-p[l] < d) r++;
    sol += (long long) r-l-1;
  }
  cout << sol << '\n';
  return 0;
}