Cod sursa(job #2080880)

Utilizator Ruxandra985Nanu 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;
}