Cod sursa(job #9847)

Utilizator cristi8Constantin-Cristian Balas cristi8 Data 27 ianuarie 2007 18:21:43
Problema Secventa 5 Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX ((1<<20) + 8)
#define HSIZE 611111

typedef unsigned int uint;
typedef long long lint;
typedef struct hnod {
  uint nr;
  int count;
  struct hnod *nxt;
} hnod;

hnod *hl[HSIZE], *hu[HSIZE], **h;
int n, L, U;
uint a[NMAX];
int l[NMAX];
int u[NMAX];
lint sol;

int hf(uint x) {
  return x % HSIZE;
}

hnod *hget(uint x) {
  hnod *q;
  for(q = h[hf(x)]; q; q = q->nxt)
    if(q->nr == x)
      return q;
  return 0;
}

int hadd(uint x) {
  int pos;
  hnod *q = hget(x);
  if(q) {
    q->count++;
    return 0;
  } else {
    q = malloc(sizeof(hnod));
    q->count = 1;
    q->nr = x;
    q->nxt = h[pos = hf(x)];
    h[pos] = q;
    return 1;
  }
}

int hdel(uint x) {
  int pos = hf(x);
  hnod *todelete = hget(x), *q;
  if(todelete->count > 1) {
    todelete->count--;
    return 0;
  }
  if(h[pos] == todelete) {
    h[pos] = todelete->nxt;
    free(todelete);
    return 1;
  }
  for(q = h[pos]; q->nxt; q = q->nxt)
    if(q->nxt == todelete) {
      q->nxt = todelete->nxt;
      free(todelete);
      return 1;
    }
  return 0; // not found
}

/* Problema1: umple v[]
  v[i] = indicele maxim al unui element pt care secventa (v[i], i) contine exact len numere distincte.
       = 0, daca nu exista o astfel de secventa

  presupune hash-ul gol si v[] initializat cu 0
*/
void prob1(int *v, int len) {
  int st, fin, l;
  hnod *q;
  st = 1; fin = 1; l = 1;
  hadd(a[1]);
  while(l < len) { // vreau len numere distincte intre st=1 si fin
    fin++;
    if(fin > n)
      return;
    if(hget(a[fin]) == 0)
      l++;
    hadd(a[fin]);
  }
  while(1) {
    while(l > len)
      l -= hdel(a[st++]);
    while(1) {
      q = hget(a[st]);
      if(q->count == 1)
        break;
      hdel(a[st++]);
    }
    v[fin] = st;
    if(++fin > n)
      break;
    l += hadd(a[fin]);
  }
}

void solve() {
  int i;
  h = hl;
  prob1(l, L);
//  memset(h, 0, sizeof(h)); // golesc repede-repede hash-ul
  h = hu;
  prob1(u, U+1);

  for(i = 1; i <= n; i++)
    sol += l[i] - u[i];
}

int main() {
  int i;
  freopen("secv5.in", "r", stdin);
  freopen("secv5.out", "w", stdout);
  scanf("%d%d%d", &n, &L, &U);
  for(i = 1; i <= n; i++)
    scanf("%u", &a[i]);
  solve();
  printf("%lld\n", sol);
  return 0;
}