Cod sursa(job #13051)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 5 februarie 2007 15:19:11
Problema Secventa 5 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

#define ui unsigned int 
#define ll long long
#define maxn 1048576
#define mod 666013
#define maxl 10

int n,x,y;
ui a[maxn];
ll sol;
vector <int> c[mod];
vector <ui> p[mod];

int add(ui x)
{
    int aux=x%mod,i;
    
    for (i=0;i<p[aux].size();i++)
      if (p[aux][i]==x)
      {
          c[aux][i]++;
          return 0;
      }
    
    p[aux].push_back(x);
    c[aux].push_back(1);
    
    return 1;
}

int extract(ui x)
{
    int aux=x%mod,i=0;
    
    while (p[aux][i]!=x) i++;
    
    if (c[aux][i]>1) 
    {
       c[aux][i]--;
       return 0;
    }
    else {
            c[aux][i]=c[aux][c[aux].size()-1];
            c[aux].pop_back();
            p[aux][i]=p[aux][p[aux].size()-1];
            p[aux].pop_back();
              
            return 1;
         }
}

ll count(int x)
{
     int i,j=0,diff=0;
     ll rez=0;
     
     memset(c,0,sizeof(c));
     memset(p,0,sizeof(p));
     
     for (i=0;i<n;i++)
     {
         diff+=add(a[i]);
		 while ((diff>=x) && (j<=i))
         {
               diff-=extract(a[j]);
               j++;
         }
         rez+=j;
     }
     
     return rez;
}

int main()
{
    freopen("secv5.in","r",stdin);
    freopen("secv5.out","w",stdout);
    
    int i;
    
    scanf("%d %d %d",&n,&x,&y);
	for (i=0;i<n;i++) scanf("%lu",&a[i]);
    
	sol=count(x);
//	printf("%lld\n",sol);
	sol=sol-count(y+1);
    
    printf("%lld\n",sol);
    
    return 0;
}