Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2467
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2467
Frequency
By OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
Byteland is a city well known for proposing varied challenges to its inhabitants. Recently, the mayor of Byteland, Joãozinho decided to propose a challenge he likes to call the Board of Frequency.
The game is as follows. Initially, a tray with dimensions N × N is data containing only 0's. Thereafter, Q operations are proposed, which can be of 4 types:
- 1 X R: Assign the R value to all numbers in the X line;
- 2 X R: Assign the R value to all numbers in the X column;
- 3 X: Print the most common value in the X line;
- 4 X: Print the most common value in column X.
Joãozinho is very good with computers, but also quite lazy. Knowing that you are one of the best programmers in the world, he decided to ask for your help to solve this problem.
Input
The first input line consists of two integers N and Q (1 ≤ N, Q ≤ 105) representing, respectively, the tray size and the number of operations. The next Q input lines will contain the Q operations. The entire first line of each will indicate the type of operation. If 1 or 2 is followed by two integer X (1 ≤ X ≤ N) and R (0 ≤ R ≤ 50). If 3 or 4, will be followed by one further integer X.
Output
For each operation type 3 or 4, its program should produce a line containing the value of the corresponding response. If a row or column have two or more values that are repeated the same number of times, you must print as many of them. For example, if a line has the values [5,7,7,2,5,2,1,3], both the 2, 5 and 7 are repeated twice, then the answer is 7 because it is the largest of the array.
| Input Sample | Output Sample |
|
5 9 3 1 1 1 2 1 3 4 1 4 4 4 2 2 2 5 2 3 5 2 4 5 3 3 |
0 4 5 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
typedef struct node *pnode;
const int MAXN = 1e5 + 10;
const int MAXR = 51;
int ultima_linha[MAXN], ultima_coluna[MAXN], atual_linha[MAXN],
atual_coluna[MAXN], iteracao;
struct node {
pnode l, r;
int size, prior;
ii key;
node(ii key) : key(key), size(1), prior(rand()), l(NULL), r(NULL) {}
};
inline int sz(pnode t) {
if (t == NULL) return 0;
return t->size;
}
inline void upd_sz(pnode t) {
if (t) t->size = sz(t->l) + 1 + sz(t->r);
}
void split(pnode t, ii key, pnode &l, pnode &r) {
if (t == NULL) {
l = r = NULL;
} else if (key < t->key) {
split(t->l, key, l, t->l);
r = t;
} else {
split(t->r, key, t->r, r);
l = t;
}
upd_sz(t);
}
void merge(pnode &t, pnode l, pnode r) {
if (l == NULL) {
t = r;
} else if (r == NULL) {
t = l;
} else if (l->prior > r->prior) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
upd_sz(t);
}
void insert(pnode &t, ii key) {
pnode L, R;
pnode aux = new node(key);
split(t, MP(key.first, key.second - 1), L, R);
merge(t, L, aux);
merge(t, t, R);
}
void erase(pnode &t, ii key) {
pnode L, mid, R;
split(t, MP(key.first, key.second - 1), L, R);
split(R, key, mid, R);
merge(t, L, R);
}
int query(pnode t, ii key) {
pnode L, R;
split(t, key, L, R);
int resp = sz(R);
merge(t, L, R);
return resp;
}
pnode raiz_linha[MAXR], raiz_coluna[MAXR];
int main() {
int n, q, r = 50;
scanf("%d %d", &n, &q);
for (int i = 0; i < = r; i++) {
raiz_linha[i] = NULL;
raiz_coluna[i] = NULL;
}
for (int i = 1; i < = n; i++) {
insert(raiz_linha[0], MP(0, i));
insert(raiz_coluna[0], MP(0, i));
}
while (q--) {
iteracao++;
int op;
scanf("%d", &op);
if (op == 1) {
int x, davez;
scanf("%d %d", &x, &davez);
erase(raiz_linha[atual_linha[x]], MP(ultima_linha[x], x));
atual_linha[x] = davez;
ultima_linha[x] = iteracao;
insert(raiz_linha[davez], MP(iteracao, x));
} else if (op == 2) {
int x, davez;
scanf("%d %d", &x, &davez);
erase(raiz_coluna[atual_coluna[x]], MP(ultima_coluna[x], x));
atual_coluna[x] = davez;
ultima_coluna[x] = iteracao;
insert(raiz_coluna[davez], MP(iteracao, x));
} else if (op == 3) {
int x;
scanf("%d", &x);
int davez = atual_linha[x];
int ultima = ultima_linha[x];
ii resp = MP(-1, -1);
ii pergunta = MP(ultima - 1, n + 1);
int tot = 0;
for (int cor = 0; cor < = r; cor++) {
if (cor == davez) continue;
int conta = query(raiz_coluna[cor], pergunta);
resp = max(resp, MP(conta, cor));
tot += conta;
}
resp = max(resp, MP(n - tot, davez));
printf("%d\n", resp.second);
} else {
int x;
scanf("%d", &x);
int davez = atual_coluna[x];
int ultima = ultima_coluna[x];
ii resp = MP(-1, -1);
ii pergunta = MP(ultima - 1, n + 1);
int tot = 0;
for (int cor = 0; cor < = r; cor++) {
if (cor == davez) continue;
int conta = query(raiz_linha[cor], pergunta);
resp = max(resp, MP(conta, cor));
tot += conta;
}
resp = max(resp, MP(n - tot, davez));
printf("%d\n", resp.second);
}
}
return 0;
}
Input
3 1
1 1 2
1 3 4
1 4 4
4 2
2 2 5
2 3 5
2 4 5
3 3
Output
4
5