Cod sursa(job #2080880)
Utilizator | Nanu Ruxandra Laura Ruxandra985 | Data | 3 decembrie 2017 16:43:19 |
---|---|---|---|
Problema | Marbles | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.71 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
int a[65][100001];
int v[65];
int main()
{
FILE *fin=fopen ("marbles.in","r");
FILE *fout=fopen ("marbles.out","w");
int n,m,i,j,sol,cer,x,y,p,u,st,dr,mid;
fscanf (fin,"%d%d",&n,&m);
for (i=1;i<=n;i++){
fscanf (fin,"%d%d",&x,&y);
v[y]++;
a[y][v[y]]=x;
}
for (i=1;i<=n;i++)
sort (a[i]+1,a[i]+v[i]+1);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d%d",&cer,&x,&y);
if (cer==0){
for (j=1;j<=n;j++){
st=1;
dr=v[j];
while (st<=dr){
mid=(st+dr)/2;
if (a[j][mid]==x)
break;
else if (a[j][mid]<x)
st=mid+1;
else dr=mid-1;
}
if (st<=dr){
a[j][mid]=x+y;
break;
}
}
}
else {
sol=0;
for (j=1;j<=n;j++){
st=1;
dr=v[j];
while (st<=dr){
mid=(st+dr)/2;
if (a[j][mid]<x)
st=mid+1;
else dr=mid-1;
}
p=st;
st=1;
dr=v[j];
while (st<=dr){
mid=(st+dr)/2;
if (a[j][mid]<y)
st=mid+1;
else dr=mid-1;
}
u=st;
sol=max(sol,u-p);
}
fprintf (fout,"%d\n",sol);
}
}
return 0;
}