Cod sursa(job #3245438)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 29 septembrie 2024 00:50:39
Problema Secventa 5 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#include <unordered_map>

#define MAXN (1<<20)

std::unordered_map<int, int> ap;

int n;

int min;
int max;

int v[MAXN];
int sp[MAXN];

int cautbin(int pos, int val){
  int s = -1;
  int d = pos+1;
  while(d-s>1){
    int m = (s+d)/2;
    if(sp[m]>sp[pos]-val) d = m;
    else s = m;
  }
  /*printf("%d %d %d\n", s, sp[pos]-(s>=0?sp[s]:0), val);*/
  if(sp[pos]-(s>=0?sp[s]:0)==val) return s;
  return -1;
}

int main(){
  FILE *fin, *fout;
  fin = fopen("secv5.in", "r");
  fscanf(fin, "%d%d%d", &n, &min, &max);
  for(int i=0; i<n; i++){
    fscanf(fin, "%d\n", &v[i]);
    sp[i] = (i>0?sp[i-1]:0)+(ap.count(v[i])==0);
    ap[v[i]]++;
    /*printf("%d ", sp[i]);*/
  }
  printf("\n");
  fclose(fin);
  
  int total = 0;
  for(int i=0; i<n; i++){
    int l = cautbin(i, max);
    int r = cautbin(i, min-1);
    /*printf("%d: %d %d %d\n", i, l, r-1, r-l);*/
    total += (r-1)-l+1;
  }

  fout = fopen("secv5.out", "w");
  fprintf(fout, "%d\n", total); 
  fclose(fout);
  return 0;
}