Cod sursa(job #2560086)

Utilizator AlexandruBrezuleanuAlexandruBrezuleanu AlexandruBrezuleanu Data 27 februarie 2020 19:14:44
Problema Marbles Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
#define MAX 80
using namespace std;
ifstream fin("marbles.in");
ofstream fout("marbles.out");
vector<int>g[MAX];
int m,n,maxim,minim=70,maxim1;
int cautbin(int culoare,int val);
int cautbin2(int culoare,int val);
int main()
{
    int i,j,poz,cul,ce,a,b,unde,x1,x2;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>poz>>cul;
        if(cul>maxim)
            maxim=cul;
        if(cul<minim)
            minim=cul;
        g[cul].push_back(poz);
    }
    for(i=minim;i<=maxim;i++)
        if(g[i].size())
        sort(g[i].begin(),g[i].end());
    for(i=1;i<=m;i++)
    {
        fin>>ce>>a>>b;

        if(ce==0)
        {
            for(j=minim;j<=maxim;j++)
                if(g[j].size())
                {
                    unde=cautbin2(j,a);
                    if(unde!=-1)
                    {
                        g[j][unde]=a+b;
                        break;
                    }
                }
        }
        else if(ce==1)
        {
            maxim1=0;
            for(j=minim;j<=maxim;j++)
            {
                x1=cautbin(j,a);
                x2=cautbin(j,b);
                if(g[j][x1]==a&&g[j][x2]==b)
                    {if(maxim1<x2-x1+1)
                    maxim1=x2-x1+1;}
                else
                    if(maxim1<x2-x1)
                    maxim1=x2-x1;
            }
            fout<<maxim1<<endl;
        }
    }
    return 0;
}
int cautbin(int culoare,int val)
{
    int st=-1,dr=g[culoare].size(),mij;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(g[culoare][mij]==val)
            return mij;
        else if(g[culoare][mij]<val)
        st=mij;
        else
            dr=mij;
    }
    return dr;

}
int cautbin2(int culoare,int val)
{
    int st=0,dr=g[culoare].size()-1,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(g[culoare][mij]==val)
            return mij;
        else if(g[culoare][mij]<val)
        st=mij+1;
        else
            dr=mij-1;
    }
    return -1;
}