selecao.cpp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
int x[MAXN],y[MAXN];

int n,k, maior;

//Calculo para um valor val quantos números menores ou iguais a ele estão na matriz
bool calc(int val)
{
    int aux = 0;
    int j = 0;
    //Passo por cada linha
    for(int i = n; i > 0; i--)
    {
        //Tento aumentar o j. Note que o j não é zerado quando mudo de linha
        while(x[i] + y[j + 1] <= val && j < n)
        {
            j++;
        }
        //Adiciono J no número de valores menores ou iguais a val na matriz
        aux += j;
    }

    //Comparo com k para a busca binária
    if(aux >= k) return true;
    return false;
}

//Busca binária na resposta
int bsearch()
{
    int ini = x[1] + y[1];
    int fim = maior;

    while(ini < fim)
    {
        int m = (ini + fim)/2;

        //Testo se a nossa resposta for m
        if(calc(m))
            fim = m;
        else
            ini = m + 1;
    }

    return fim;
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k;

    int ax,bx,cx,mx; cin >> ax >> bx >> cx >> mx;
    int ay,by,cy,my; cin >> ay >> by >> cy >> my;

    x[1] = ax;
    y[1] = ay;

    for(int i = 2; i <= n; i++)
    {
        x[i] = (bx + cx*x[i-1])%mx;
        y[i] = (by + cy*y[i-1])%my;
    }

    //Ordeno os vetores para organizar a matriz
    sort(x + 1, x + (n + 1));
    sort(y + 1, y + (n + 1));

    maior = x[n] + y[n];

    cout << bsearch();

}