Comentário por Murilo Maeda
Nesse problema há duas dificuldades principais: o tamanho grande da matriz, então não podemos nem percorrê-la nem mantê-la em uma matriz, e a forma desorganizada que os números aparecem na matriz, não há um padrão que nos permita concluir coisas sobre a posição e organização de números na matriz.
Para resolver o primeiro problema, basta simplesmente não mantermos a matriz. Vamos manter somente os vetores $$x$$ e $$y$$ e quando precisarmos de um valor, só somamos os valores necessários de $$x$$ e $$y$$.
Agora, vamos resolver o segundo problema.
Note que, como queremos encontrar os $$K$$ menores números, a posição deles na matriz não importa. Por isso, podemos ordenar os vetores $$x$$ e $$y$$, do menor para o maior e formar a matriz $$M$$ na qual $$M_{ij} = x[i] + y[j]$$ . Agora, temos duas propriedades dessa matriz: em uma mesma linha, se a percorrermos de $$1$$ a $$N$$, os valores estarão dispostos em ordem não decrescente. O mesmo ocorre quando percorremos uma coluna de $$1$$ a $$N$$.
A partir disso, vamos analizar o que acontece quando queremos saber quantos valores menores ou iguais a um determinado valor $$c$$ estão na matriz $$M$$. Note que, se encontrarmos em uma determinada linha $$l$$ o índice $$k$$ de modo que o valor $$M_{lk}$$ é o maior valor maior ou igual a $$c$$ na linha $$l$$, nas linhas com índice menor que $$l$$, o maior valor maior ou igual a $$c$$ vai estar em um índice maior ou igual a $$k$$, já que os valores em uma coluna e em uma linha estão em ordem não decrescente. Por isso, para um determinado número $$c$$, para descobrir quantos valores menores ou iguais a ele estão na matriz $$M$$, podemos simplesmente fazer o seguinte: passamos pela linha n e pegamos $$k_n$$ e o somamos no número de valores menores ou iguais a $$c$$. Para uma linha $$l$$: a percorremos a partir do índice $$k_{l+1}$$ enquanto os valores forem menores ou iguais a $$c$$. Paramos no índice $$k_{l}$$ e somamos $$k_l$$ no número de valores menores ou iguais a $$c$$.
Com isso, podemos calcular em $$O(n)$$ quantos valores são menores ou iguais a $$c$$ na matrisz $$M$$. Então, basta fazermos uma busca binária na resposta, tentando encontrar o valor que queremos. Fazemos isso chutando o número da resposta, checando quantos valores são menores ou iguais a ele em $$M$$ e em seguida comparando esse resultado com $$k$$.
Segue o código para maior esclarecimento:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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(); | |
| } |