Cod sursa(job #163693)
Utilizator | Serban Andrei Stan savim | Data | 22 martie 2008 14:58:25 |
---|---|---|---|
Problema | Marbles | Scor | 0 |
Compilator | cpp | Status | done |
Runda | preONI 2008, Runda Finala, Clasele 5-8 | Marime | 1.58 kb |
#include <stdio.h>
int max,p1,p2,x,y,p,q,i,j,k,n,m,r;
int a[100010][2];
int v[100010][65];
int main()
{
freopen("marbles.in","r",stdin);
freopen("marbles.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1; i<=n; i++)
{
scanf("%d %d",&a[i][0],&a[i][1]);
for (j=1; j<=64; j++)
v[i][j]=v[i-1][j];
v[i][a[i][1]]++;
}
for (i=1; i<=m; i++)
{
scanf("%d %d %d",&k,&x,&y);
if (k==0)
{
p=0;q=n+1;
while (p+1<q)
{
r=(p+q)/2;
if (a[r][0]>x) q=r;
else if (a[r][0]<x)p=r;
else break;
}
a[r][0]=a[r][0]+y;
}
else
{
if (x>y)
{
p=x;x=y;y=p;
}
p1=1;p=0;q=n+1;
while (p+1<q)
{
r=(p+q)/2;
if (a[r][0]>=x)
{
q=r;
p1=r;
}
else if (a[r][0]<x) p=r;
}
p2=n;p=0;q=n+1;
while (p+1<q)
{
r=(p+q)/2;
if (a[r][0]<=y)
{
p=r;
p2=r;
}
else if (a[r][0]>y) q=r;
}
p1--;max=0;
for (j=1; j<=64; j++)
if (v[p2][j]-v[p1][j]>max) max=v[p2][j]-v[p1][j];
printf("%d\n",max);
}
}
return 0;
}