A11462. Tournament
编程题
普及/提高-
知识点
题目描述
Recently a tournament in $k$ kinds of sports has begun in Berland. Vasya wants to make money on the bets.
The scheme of the tournament is very mysterious and not fully disclosed. Competitions are held back to back, each of them involves two sportsmen who have not left the tournament yet. Each match can be held in any of the $k$ kinds of sport. Loser leaves the tournament. The last remaining sportsman becomes the winner. Apart of this, the scheme can be arbitrary, it is not disclosed in advance.
Vasya knows powers of sportsmen in each kind of sport. He believes that the sportsmen with higher power always wins.
The tournament is held every year, and each year one new participant joins it. In the first tournament, only one sportsman has participated, in the second there were two sportsmen, and so on. Vasya has been watching the tournament for the last $n$ years. Help him to find the number of possible winners for each of the $n$ tournaments.
The scheme of the tournament is very mysterious and not fully disclosed. Competitions are held back to back, each of them involves two sportsmen who have not left the tournament yet. Each match can be held in any of the $k$ kinds of sport. Loser leaves the tournament. The last remaining sportsman becomes the winner. Apart of this, the scheme can be arbitrary, it is not disclosed in advance.
Vasya knows powers of sportsmen in each kind of sport. He believes that the sportsmen with higher power always wins.
The tournament is held every year, and each year one new participant joins it. In the first tournament, only one sportsman has participated, in the second there were two sportsmen, and so on. Vasya has been watching the tournament for the last $n$ years. Help him to find the number of possible winners for each of the $n$ tournaments.
输入格式
The first line contains two integers $n$ and $k$ ( $1<=n<=5·10^{4}$ , $1<=k<=10$ ) — the number of tournaments and the number of kinds of sport, respectively.
Each of the next $n$ lines contains $k$ integers $s_{i1},s_{i2},...,s_{ik}$ ( $1<=s_{ij}<=10^{9}$ ), where $s_{ij}$ is the power of the $i$ -th sportsman in the $j$ -th kind of sport. The sportsman with higher powers always wins. It's guaranteed that for any kind of sport all of these powers are distinct.
Each of the next $n$ lines contains $k$ integers $s_{i1},s_{i2},...,s_{ik}$ ( $1<=s_{ij}<=10^{9}$ ), where $s_{ij}$ is the power of the $i$ -th sportsman in the $j$ -th kind of sport. The sportsman with higher powers always wins. It's guaranteed that for any kind of sport all of these powers are distinct.
输出格式
For each of the $n$ tournaments output the number of contenders who can win.
输入输出样例
输入 #1
3 2 1 5 5 1 10 10
输出 #1
1 2 1
输入 #2
3 2 2 2 3 3 1 10
输出 #2
1 1 3
输入 #3
3 2 2 3 1 1 3 2
输出 #3
1 1 2
说明/提示
In the first sample:
In the first tournament there is only one sportsman, and he is the winner.
In the second tournament, there are two sportsmen, and everyone can defeat another, depending on kind of sports.
In the third tournament, the third sportsman in the strongest in both kinds of sports, so he is the winner regardless of the scheme.
In the first tournament there is only one sportsman, and he is the winner.
In the second tournament, there are two sportsmen, and everyone can defeat another, depending on kind of sports.
In the third tournament, the third sportsman in the strongest in both kinds of sports, so he is the winner regardless of the scheme.