Cod sursa(job #2646095)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 30 august 2020 20:36:18
Problema Marbles Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>

#define NMAX 100003
#define ll long long

using namespace std;

ll n,m,i,j,cer,a,b,ind,st,dr,hmax;
ll color[100];

struct bile{
    ll x,c;
}v[NMAX];

bool cmp(bile a,bile b){
    return (a.x<b.x);
}

ll cautare_binara(ll nr){
    ll st=1,dr=n,mid=0;

    while(st<=dr){
        mid=(st+dr)/2;

        if(v[mid].x==nr)
            return mid;
        else if(nr>v[mid].x)
            st=mid+1;
        else
            dr=mid-1;

    }


}
ll apropiat(ll nr,ll val){
    ll st=1,dr=n,mid=0;

    while(st+1<dr){
        mid=(st+dr)/2;

        if(v[mid].x==nr)
            return mid;
        else if(nr>v[mid].x)
            st=mid;
        else
            dr=mid;

    }

    if(!val){
        if(v[st].x<v[st+1].x)
            return st+1;
        return st;
    }else{
        if(v[st].x>v[st+1].x)
            return st;

        return st+1;
    }


}


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

    scanf("%lli%lli",&n,&m);

    for(i=1;i<=n;i++)
        scanf("%lli%lli",&v[i].x,&v[i].c);

    sort(v+1,v+n+1,cmp);

    for(i=1;i<=m;i++){
        scanf("%lli%lli%lli",&cer,&a,&b);

        if(!cer){
            ind=cautare_binara(a);
            v[ind].x=v[ind].x+b;
           // printf("%d",ind);

        }else{
            st=apropiat(a,0);
            dr=apropiat(b,1);

            hmax=-1;
            for(j=st;j<=dr;j++)
                if(v[j].x)
                    color[v[j].c]++,hmax=max(hmax,color[v[j].c]);

            //printf("%d %d\n",st,dr);

            printf("%lli\n",hmax);

            for(j=0;j<=70;j++)
                color[j]=0;
        }

    }

    /*for(i=1;i<=n;i++)
        printf("%d %d\n",v[i].x,v[i].c);*/


    return 0;
}