Cod sursa(job #2847602)

Utilizator Madalin_IonutFocsa Ionut-Madalin Madalin_Ionut Data 11 februarie 2022 08:57:27
Problema Marbles Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("marbles.in");
ofstream fout("marbles.out");

int n, m, max_color;
int a[64][100003];
int len[64];


void Citire()
{
    int i, coord, culoare;
    fin >> n >> m;
    for(i = 1;i <= n;i++)
    {
        fin >> coord >> culoare;
        a[culoare][++len[culoare]] = coord;
        max_color = max(max_color, culoare);
    }
}

///cauta un numar mai mare sau egal cu numarul furnizat
int CautBin_MMEg(int culoare, int poz)
{
    int st, dr, mij, p;
    st = 1; dr = len[culoare];
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(a[culoare][mij] >= poz)
        {
            dr = mij - 1;
            p = mij;
        }
        else st = mij + 1;
    }
    return p;
}

///cauta un numar mai mic sau egal cu numarul furnizat
int CautBin_mmEg(int culoare, int poz)
{
    int st, dr, mij, p;
    st = 1; dr = len[culoare];
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(a[culoare][mij] <= poz)
        {
            st = mij + 1;
            p = mij;
        }
        else dr = mij - 1;
    }
    return p;
}

int MassCautBin_p1(int x, int y)
{
    int i, st, dr, max_sum = 0;
    for(i = 1;i <= max_color;i++)
    {
        st = CautBin_MMEg(i, x);
        dr = CautBin_mmEg(i, y);
        max_sum = max(max_sum, dr - st + 1);
    }
    return max_sum;
}

void MassCautBin_p0(int x, int y)
{
    int i, poz = 0;
    for(i = 1;i <= max_color;i++)
    {
        poz = CautBin_mmEg(i, x);
        if(a[i][poz] == x)
        {
            a[i][poz] += y;
            return;
        }
    }
}

void Rezolvare()
{
    int i, p, x, y;
    for(i = 1;i <= max_color;i++)
        sort(a[i] + 1, a[i] + len[i] + 1);
    for(i = 1;i <= m;i++)
    {
        fin >> p >> x >> y;
        if(p == 1)
            fout << MassCautBin_p1(x, y) << "\n";
        else
            MassCautBin_p0(x, y);
    }
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}