Cod sursa(job #120438)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 5 ianuarie 2008 14:56:26
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define maxn 1048576 
#define nr 666013
#define mod 131072
#define ui unsigned int
#define ll long long
#define uc unsigned char
#define pb push_back
#define pp pop_back()
#define maxl 13

int n,x,y;
ll sol;
ui a[maxn];
vector <ui> b[mod];
vector <uc> c[mod];
char v[maxl];

inline int add(ui x)
{
	ui y = (x * nr) >> 15;
	int l = b[y].size(), i;

	for (i=0;i<l;i++)
		if (b[y][i] == x)
		{
			c[y][i]++;
			return 0;
		}

	b[y].pb(x);
	c[y].pb(1);
	return 1;
}

inline int erase(ui x)
{
	ui y = ((ui) x * nr) >> 15;
	int l = b[y].size(), i;

	for (i=0;i<l;i++)
		if (b[y][i] == x)
		{	
			if (c[y][i]>1) 
			{
				c[y][i] --;
				return 0;
			}
			else {
					c[y][i] = c[y][l-1];
					b[y][i] = b[y][l-1];
					b[y].pp;
					c[y].pp;
					return 1;
				 }
			break;
		}

	return 0;
}

ll solve(int x)
{
	int i,j,v=0;
	ll rez=0;

	for (i=0, j=0;i<n;i++)
	{
		v += add(a[i]);
		for (;j<=i && v>=x;j++) v -= erase(a[j]);

		rez += j;
	}

	return rez;
}

int main()
{
	freopen("secv5.in","r",stdin);
	freopen("secv5.out","w",stdout);

	scanf("%d %d %d ",&n,&x,&y);

	int i,j,l;
	
	for (i=0;i<n;i++)
	{
		scanf("%s ", v);
		l = strlen(v);

		for (j=0;j<l;j++) a[i] = a[i] * 10 + v[j] - '0';
	}

//	sol = solve(x);

//	sol -= solve(y+1);

	printf("%lld\n",sol);

	return 0;
}