C - Dislike Foods
Source: atcoder
Difficulty: 300

Problem Statement
The AtCoder Restaurant uses
N
types of ingredients numbered from
1
to
N
.
The restaurant offers
M
dishes numbered from
1
to
M
. Dish
i
uses
K_i
types of ingredients, namely
A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}
.
Snuke currently dislikes all
N
ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients.
Over the next
N
days, he will overcome his dislikes one ingredient per day. On day
i
, he overcomes ingredient
B_i
, and from then on he no longer dislikes it.
For each
i=1,2,\ldots,N
, find:
the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient
B_i
on day
i
.
Constraints
1 \leq N \leq 3 \times 10^{5}
1 \leq M \leq 3 \times 10^{5}
1 \leq K_i \leq N
(1 \leq i \leq M)
The sum of
K_i
is at most
3 \times 10^{5}
.
1 \leq A_{i,j} \leq N
(1 \leq i \leq M, 1 \leq j \leq K_i)
A_{i,j} \neq A_{i,k}
(1 \leq i \leq M, j \neq k)
1 \leq B_i \leq N
(1 \leq i \leq N)
B_i \neq B_j
(i \neq j )
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
K_1
A_{1,1}
A_{1,2}
\ldots
A_{1,K_1}
K_2
A_{2,1}
A_{2,2}
\ldots
A_{2,K_2}
\vdots
K_M
A_{M,1}
A_{M,2}
\ldots
A_{M,K_M}
B_1
B_2
\ldots
B_N
Output
Print
N
lines. The
k
-th line should contain the answer for
i=k
.
Sample Input 1
5 4
2 1 2
3 3 4 5
3 1 2 5
1 3
1 3 2 5 4
Sample Output 1
0
1
2
3
4
Snuke overcomes his disliked ingredients as follows:
Day
1
: He overcomes ingredient
1
. At this time, every dish still uses a disliked ingredient, so print
0
.
Day
2
: He overcomes ingredient
3
. Dish
4
no longer uses any disliked ingredient and becomes edible; all other dishes still use disliked ingredients, so print
1
.
Day
3
: He overcomes ingredient
2
. Dish
1
no longer uses any disliked ingredient and becomes edible; all dishes except
1
and
4
still use disliked ingredients, so print
2
.
Day
4
: He overcomes ingredient
5
. Dish
3
no longer uses any disliked ingredient and becomes edible; all dishes except
1
,
3
, and
4
still use disliked ingredients, so print
3
.
Day
5
: He overcomes ingredient
4
. Dish
2
no longer uses any disliked ingredient and becomes edible; now all dishes have no disliked ingredients, so print
4
.
Sample Input 2
9 8
1 4
5 6 9 7 4 3
4 2 4 1 3
1 1
5 7 9 8 1 5
2 9 8
1 2
1 1
6 5 2 7 8 4 1 9 3
Sample Output 2
0
0
1
1
1
2
4
6
8

C++ solution:
#include <bits/stdc++.h>

using namespace std;

basic_string < int > a[300300];

int cnt[300300], ord[300300];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, k;
	cin >> n >> m;
	for(int i = 0; i < m; ++ i) {
		cin >> k;
		a[i].resize(k);
		for(auto &j : a[i]) {
			cin >> j;
		}
	}
	for(int i = 0, b; ++ i <= n; cin >> b, ord[b] = i);
	for(int i = 0; i < m; ++ i) {
		k = 0;
		for(auto &j : a[i]) {
			k = max(k, ord[j]);
		}
		++ cnt[k];
	}
	for(int i = 0; ++ i <= n; cout << (cnt[i] += cnt[i - 1]) << '\n');
}

Go solution:
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
	// "regexp"
)

var (
	// Scanner は 1 行ずつ読む
	sc = bufio.NewScanner(os.Stdin)
	// 標準出力に書き出す
	wr = bufio.NewWriter(os.Stdout)
)

const (
	mod = 998244353
	// mod = int(1e9 + 7)
	INF = 1 << 62
)

func solve() {
	// START
	n, m := readI2()
	a := make([][]int, m)
	for i := 0; i < m; i++ {
		k := readI()
		a[i] = newInts(k, 0)
		for j := 0; j < k; j++ {
			a[i][j] = readI() - 1
		}
	}
	b := newInts(n, 0)
	for i := 0; i < n; i++ {
		b[readI()-1] = i
	}
	plus := make([]int, n)
	for i := 0; i < m; i++ {
		sort.SliceStable(a[i], func(p, q int) bool { return b[a[i][p]] < b[a[i][q]] })
		plus[b[a[i][len(a[i])-1]]]++
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans += plus[i]
		print(ans)
	}
	// END
}

//

//

// main 関数
func main() {
	// 空白区切りで読む込むように設定
	sc.Split(bufio.ScanWords)
	// 最大読み込み文字数を2*10^5に対応
	// 2*10^6 のバッファを確保
	sc.Buffer(make([]byte, 2000000*1+1), 2000000)
	// 全部書き出す
	defer wr.Flush()

	solve()
}

//////////////////////////////////////
// 標準入出力に関わる関数
//////////////////////////////////////

// 整数の読み込み
func readI() int {
	// 空白区切りで文字列として読み込む
	sc.Scan()
	// Text() メソッドで読み込んだものを取り出す
	// 文字列を整数に変換
	i, _ := strconv.Atoi(sc.Text())
	return i
}

// 整数列の読み込み
func readInts(n int) []int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = readI()
	}
	return arr
}

// [value, index] で整数列の読み込み
func readIntsWithIdx(n int) [][]int {
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, 2)
		arr[i][0], arr[i][1] = readI(), i
	}
	return arr
}

// n*m 2次元整数列の読み込み
func readTwoInts(n int, m int) [][]int {
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
		arr[i] = readInts(m)
	}
	return arr
}

// 2つの長さnの整数列を行ずつ読み込み
func readIntsARow2(n int) ([]int, []int) {
	arr1 := make([]int, n)
	arr2 := make([]int, n)
	for i := 0; i < n; i++ {
		arr1[i], arr2[i] = readI2()
	}
	return arr1, arr2
}

// 3つの長さnの整数列を行ずつ読み込み
func readIntsARow3(n int) ([]int, []int, []int) {
	arr1 := make([]int, n)
	arr2 := make([]int, n)
	arr3 := make([]int, n)
	for i := 0; i < n; i++ {
		arr1[i], arr2[i], arr3[i] = readI3()
	}
	return arr1, arr2, arr3
}

// 4つの長さnの整数列を行ずつ読み込み
func readIntsARow4(n int) ([]int, []int, []int, []int) {
	arr1 := make([]int, n)
	arr2 := make([]int, n)
	arr3 := make([]int, n)
	arr4 := make([]int, n)
	for i := 0; i < n; i++ {
		arr1[i], arr2[i], arr3[i], arr4[i] = readI4()
	}
	return arr1, arr2, arr3, arr4
}

// idx0 を開けて n 個の整数を n+1 要素の整数列へ読み込み
func readInts0(n int) []int {
	arr := make([]int, n+1)
	for i := 1; i <= n; i++ {
		arr[i] = readI()
	}
	return arr
}

func readI2() (int, int)                { return readI(), readI() }
func readI3() (int, int, int)           { return readI(), readI(), readI() }
func readI4() (int, int, int, int)      { return readI(), readI(), readI(), readI() }
func readI5() (int, int, int, int, int) { return readI(), readI(), readI(), readI(), readI() }
func readI6() (int, int, int, int, int, int) {
	return readI(), readI(), readI(), readI(), readI(), readI()
}

func readInts2(n int) ([]int, []int)        { return readInts(n), readInts(n) }
func readInts3(n int) ([]int, []int, []int) { return readInts(n), readInts(n), readInts(n) }
func readInts4(n int) ([]int, []int, []int, []int) {
	return readInts(n), readInts(n), readInts(n), readInts(n)
}

// 文字列の読み込み
func readS() string {
	sc.Scan()
	return sc.Text()
}

// []byte で文字列の読み込み
func readSBytes() []byte {
	sc.Scan()
	return []byte(sc.Text())
}

// 文字列列の読み込み
func readStrings(n int) []string {
	arr := make([]string, n)
	for i := 0; i < n; i++ {
		arr[i] = readS()
	}
	return arr
}

func readS2() (string, string)                 { return readS(), readS() }
func readS3() (string, string, string)         { return readS(), readS(), readS() }
func readS4() (string, string, string, string) { return readS(), readS(), readS(), readS() }
func readS5() (string, string, string, string, string) {
	return readS(), readS(), readS(), readS(), readS()
}

func readSBytes2() ([]byte, []byte)         { return readSBytes(), readSBytes() }
func readSBytes3() ([]byte, []byte, []byte) { return readSBytes(), readSBytes(), readSBytes() }
func readSBytes4() ([]byte, []byte, []byte, []byte) {
	return readSBytes(), readSBytes(), readSBytes(), readSBytes()
}
func readSBytes5() ([]byte, []byte, []byte, []byte, []byte) {
	return readSBytes(), readSBytes(), readSBytes(), readSBytes(), readSBytes()
}

// 外側をxで覆ってh*wのボードを読み込む
func readBoard(h, w int, x byte) [][]byte {
	board := newTwoBytes(h+2, w+2, x)
	for i := 1; i <= h; i++ {
		t := readSBytes()
		for j := 1; j <= w; j++ {
			board[i][j] = t[j-1]
		}
	}
	return board
}

// 改行なしで単体出力
func printB(x ...interface{}) {
	fmt.Fprint(wr, x...)
}

// 最後に改行ありで出力 並列の場合はそのまま[]byteも[]intも出力
func print(x ...interface{}) {
	if len(x) == 1 {
		switch x[0].(type) {
		case []byte:
			fmt.Fprintln(wr, string(x[0].([]byte)))
		case []int:
			printInts(x[0].([]int))
		default:
			fmt.Fprintln(wr, x...)
		}
	} else {
		fmt.Fprintln(wr, x...)
	}
}

// Yesを出力
func printY() {
	fmt.Fprintln(wr, "Yes")
}

// Noを出力
func printN() {
	fmt.Fprintln(wr, "No")
}

// 整数列を空白区切りで出力
func printInts(x []int) {
	for i := 0; i < len(x); i++ {
		fmt.Fprint(wr, x[i])
		fmt.Fprint(wr, " ")
	}
	fmt.Fprintln(wr)
}

// 整数列を改行区切りで出力
func printIntsln(x []int) {
	for i := 0; i < len(x); i++ {
		fmt.Fprintln(wr, x[i])
	}
}

// 文字列列を空白区切りで出力
func printStrings(x []string) {
	for i := 0; i < len(x); i++ {
		fmt.Fprint(wr, x[i])
		fmt.Fprint(wr, " ")
	}
	fmt.Fprintln(wr)
}

// 文字列列を改行区切りで出力
func printStringsln(x []string) {
	for i := 0; i < len(x); i++ {
		fmt.Fprintln(wr, x[i])
	}
}

// []byte を文字列に変換して出力
func printBytes(s []byte) {
	print(string(s))
}

//////////////////////////////////////
// Basinc Functions
//////////////////////////////////////

// min(a, b)
func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

// min(a, b) int64
func min64(a, b int64) int64 {
	if a < b {
		return a
	} else {
		return b
	}
}

// min(a, b) float64
func minFloat(a, b float64) float64 {
	if a < b {
		return a
	} else {
		return b
	}
}

// max(a, b)
func max(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}

// max(a, b) int64
func max64(a, b int64) int64 {
	if a < b {
		return b
	} else {
		return a
	}
}

// min(a, b) float64
func maxFloat(a, b float64) float64 {
	if a < b {
		return b
	} else {
		return a
	}
}

// |a|
func abs(a int) int {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

// |a| int64
func abs64(a int64) int64 {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

// |a| float64
func absFloat(a float64) float64 {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

// p^n
func power(p, n int) int {
	res := 1
	x := p
	for n != 0 {
		if n%2 == 1 {
			res *= x
		}
		n /= 2
		x = x * x
	}
	return res
}

// p^n int64
func power64(p, n int64) int64 {
	res := int64(1)
	x := p
	for n != 0 {
		if n%2 == 1 {
			res *= x
		}
		n /= 2
		x = x * x
	}
	return res
}

// p^n float64
func powerFloat(p float64, n int) float64 {
	res := float64(1)
	x := p
	for n != 0 {
		if n%2 == 1 {
			res *= x
		}
		n /= 2
		x = x * x
	}
	return res
}

// sum a[]
func sumInts(a []int) int {
	res := 0
	for i := range a {
		res += a[i]
	}
	return res
}

// n!
func factorial(n int) int {
	res := 1
	for i := 2; i <= n; i++ {
		res *= i
	}
	return res
}

// prime check
func isPrime(n int) bool {
	if n == 1 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

// 整数列昇順ソート
func sortInts(x []int) {
	sort.Ints(x)
}

// 整数列降順ソート
func sortIntsR(x []int) {
	sort.SliceStable(x, func(i, j int) bool { return x[i] > x[j] })
}

// 整数列 a を昇順にし、その ind で b を並び替える書き換えをする
func sortIntsAscendWith(a []int, b []int) {
	x := make([][2]int, len(a))
	for i := range x {
		x[i] = [2]int{a[i], b[i]}
	}
	sort.SliceStable(x, func(i, j int) bool { return x[i][0] < x[j][0] })
	for i := range x {
		a[i] = x[i][0]
		b[i] = x[i][1]
	}
}

// 整数列 a を降順にし、その ind で b を並び替える書き換えをする
func sortIntsDeascendWith(a []int, b []int) {
	x := make([][2]int, len(a))
	for i := range x {
		x[i] = [2]int{a[i], b[i]}
	}
	sort.SliceStable(x, func(i, j int) bool { return x[i][0] > x[j][0] })
	for i := range x {
		a[i] = x[i][0]
		b[i] = x[i][1]
	}
}

// 整数列を逆順にする
func reverseInts(x []int) {
	y := copyInts(x)
	n := len(x)
	for i := range x {
		x[i] = y[n-1-i]
	}
}

// 文字列を逆順にする
func reverseString(s string) string {
	x := strings.Split(s, "")
	sort.SliceStable(x, func(i, j int) bool { return i > j })
	return strings.Join(x, "")
}

// 文字列を辞書順にソート
func sortString(s string) string {
	x := strings.Split(s, "")
	sort.SliceStable(x, func(i, j int) bool { return x[i] < x[j] })
	return strings.Join(x, "")
}

// []byteを辞書順にソート
func sortBytes(s []byte) {
	sort.SliceStable(s, func(i, j int) bool { return s[i] < s[j] })
}

// []byteを逆順にする
func reverseBytes(s []byte) {
	sort.SliceStable(s, func(i, j int) bool { return i > j })
}

// 辞書的に次の文字列（ない場合はfalse）
func nextPermutationString(s string) (bool, string) {
	// maxi は連続2文字が辞書順にならなくなる一番手前の場所
	// 2167543 なら 6 の位置
	// ここより後はもう増やせない 7543 が最大
	maxi, maxj := 0, 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] < s[i+1] {
			maxi = i
		}
	}
	// maxj は maxi の文字より辞書的に大きいものの一番後ろの場所
	// 2167543 では 7 の位置
	for j := 0; j < len(s); j++ {
		if s[maxi] < s[j] {
			maxj = j
		}
	}
	if maxi == maxj {
		return false, s
	}
	// maxi と maxj を swap する
	// 2176543
	var x string
	if maxi < maxj {
		x = s[:maxi] + s[maxj:maxj+1] + s[maxi+1:maxj] + s[maxi:maxi+1] + s[maxj+1:]
	} else {
		x = s[:maxj] + s[maxi:maxi+1] + s[maxj+1:maxi] + s[maxj:maxj+1] + s[maxi+1:]
	}
	// もとの maxi の位置より後ろを逆にする
	// 2173456
	return true, x[:maxi+1] + reverseString(x[maxi+1:])
}

// []byte を辞書的に次の文字列に書き換える（ない場合はfalse）
func nextPermutationBytes(s []byte) bool {
	maxi, maxj := 0, 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] < s[i+1] {
			maxi = i
		}
	}
	for j := 0; j < len(s); j++ {
		if s[maxi] < s[j] {
			maxj = j
		}
	}
	if maxi == maxj {
		return false
	}
	s[maxi], s[maxj] = s[maxj], s[maxi]
	reverseBytes(s[maxi+1:])
	return true
}

// "123...n" という文字列を返す
func numStringFrom1(n int) string {
	str := ""
	for i := 1; i <= n; i++ {
		str += strconv.Itoa(i)
	}
	return str
}

// "012...n" という文字列を返す
func numStringFrom0(n int) string {
	str := ""
	for i := 0; i <= n; i++ {
		str += strconv.Itoa(i)
	}
	return str
}

// 文字列としての数字のi文字目の数字を返す（iは0から）
func numOf(s string, i int) int {
	res, _ := strconv.Atoi(s[i : i+1])
	return res
}

// 0 ~ 9 の文字としての byte 1文字を int に変換
func byteToInt(b byte) int {
	return int(b) - 48
}

// 0 ~ 9 の int を byte 1文字に変換
func intToByte(i int) byte {
	return byte(i) + 48
}

// 整数列を init で初期化して作成
func newInts(size int, init int) []int {
	arr := make([]int, size)
	if init == 0 {
		return make([]int, size)
	}
	for i := range arr {
		arr[i] = init
	}
	return arr
}

func newInts2(size int, init int) ([]int, []int) { return newInts(size, init), newInts(size, init) }
func newInts3(size int, init int) ([]int, []int, []int) {
	return newInts(size, init), newInts(size, init), newInts(size, init)
}
func newInts4(size int, init int) ([]int, []int, []int, []int) {
	return newInts(size, init), newInts(size, init), newInts(size, init), newInts(size, init)
}
func newInts5(size int, init int) ([]int, []int, []int, []int, []int) {
	return newInts(size, init), newInts(size, init), newInts(size, init), newInts(size, init), newInts(size, init)
}

// n*m 2次元整数列を init で初期化して作成
func newTwoInts(n int, m int, init int) [][]int {
	arr := make([][]int, n)
	if init == 0 {
		for i := range arr {
			arr[i] = make([]int, m)
		}
	} else {
		for i := range arr {
			arr[i] = newInts(m, init)
		}
	}
	return arr
}

// 整数列のコピー
func copyInts(x []int) []int {
	res := make([]int, len(x))
	copy(res, x)
	return res
}

// 2次元整数列のコピー
func copyTwoInts(x [][]int) [][]int {
	n := len(x)
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, len(x[i]))
		copy(res[i], x[i])
	}
	return res
}

// 初期値が init で n 文字の []byte を作成
func newBytes(n int, init byte) []byte {
	arr := make([]byte, n)
	for i := range arr {
		arr[i] = init
	}
	return arr
}

// 初期値 init で h * w の [][]byte を作成
func newTwoBytes(h, w int, init byte) [][]byte {
	arr := make([][]byte, h)
	for i := 0; i < h; i++ {
		arr[i] = newBytes(w, init)
	}
	return arr
}

// []byteのコピー
func copyBytes(x []byte) []byte {
	res := make([]byte, len(x))
	copy(res, x)
	return res
}

// 2次元[]byteのコピー
func copyTwoBytes(x [][]byte) [][]byte {
	n := len(x)
	res := make([][]byte, n)
	for i := 0; i < n; i++ {
		res[i] = make([]byte, len(x[i]))
		copy(res[i], x[i])
	}
	return res
}

//////////////////////////////////////
// mod
//////////////////////////////////////

// a + b mod
func modAdd(a, b int) int {
	res := (a + b) % mod
	if res < 0 {
		res += mod
	}
	return res
}

// a - b mod
func modSub(a, b int) int {
	res := (a - b) % mod
	if res < 0 {
		res += mod
	}
	return res
}

// a * b mod
func modMul(a, b int) int {
	a %= mod
	b %= mod
	res := (a * b) % mod
	if res < 0 {
		res += mod
	}
	return res
}

// p^n mod
func modPower(p, n int) int {
	res := 1
	x := p % mod
	for n != 0 {
		if n%2 == 1 {
			res *= x
			res %= mod
		}
		n /= 2
		x = (x * x) % mod
	}
	return res
}

// a^(-1) mod
func modInv(a int) int {
	b, u, v := mod, 1, 0
	for b != 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= mod
	if u < 0 {
		u += mod
	}
	return u
}

// a / b mod
func modDiv(a, b int) int {
	a %= mod
	res := a * modInv(b)
	res %= mod
	return res
}

// a! mod
func modFact(a int) int {
	res := a
	for a > 1 {
		a--
		res = modMul(res, a)
	}
	if res < 0 {
		res += mod
	}
	return res
}

// nPr mod
func modP(n, r int) int {
	res := n
	for r > 1 {
		n--
		r--
		res = modMul(res, n)
	}
	if res < 0 {
		res += mod
	}
	return res
}

// nCr mod
func modC(n, r int) int {
	return modDiv(modP(n, r), modFact(r))
}

//////////////////////////////////////////////////////////////
// Pos
//////////////////////////////////////////////////////////////

// 2次元座標
type Pos struct {
	x int
	y int
}

// Pos の読み込み
func readPos() Pos {
	return Pos{readI(), readI()}
}

func readPos2() (Pos, Pos) { return Pos{readI(), readI()}, Pos{readI(), readI()} }

// Pos 列を読み込み
func readPoss(n int) []Pos {
	arr := make([]Pos, n)
	for i := 0; i < n; i++ {
		arr[i] = readPos()
	}
	return arr
}

// 長さ
func length(p Pos) float64 {
	t := p.x*p.x + p.y*p.y
	return math.Sqrt(float64(t))
}

// ユークリッド距離
func distance(p, q Pos) float64 {
	t := power(p.x-q.x, 2) + power(p.y-q.y, 2)
	return math.Sqrt(float64(t))
}

//////////////////////////////////////////////////////////////
// Self-Balancing Binary Search Tree 平衡二分探索木 AVL木
//////////////////////////////////////////////////////////////

type AVLNode struct {
	key    int
	height int
	left   *AVLNode
	right  *AVLNode
}

// 左の子を取得

func (n *AVLNode) getLeft() *AVLNode {
	if n == nil {
		return nil
	}
	return n.left
}

// 右の子を取得

func (n *AVLNode) getRight() *AVLNode {
	if n == nil {
		return nil
	}
	return n.right
}

// 高さを取得

// nilなら0
func (n *AVLNode) getHeight() int {
	if n == nil {
		return 0
	}
	return n.height
}

// keyを取得

// nilなら-1
func (n *AVLNode) getKey() int {
	if n == nil {
		return -1
	}
	return n.key
}

// 高さを更新

func (n *AVLNode) updateHeight() {
	if n == nil {
		return
	}
	n.height = 1 + max(n.left.getHeight(), n.right.getHeight())
}

// 左回転：nの右の子が新たな根となる
// 右の子の左の子はnの右の子に新しくなる

func (n *AVLNode) rotateLeft() *AVLNode {
	if n.getRight() == nil {
		return n
	}
	newRoot := n.getRight()
	n.right = newRoot.getLeft()
	newRoot.left = n

	newRoot.updateHeight()
	n.updateHeight()
	return newRoot
}

// 右回転：nの左の子が新たな根となる
// 左の子の右の子はnの左の子に新しくなる

func (n *AVLNode) rotateRight() *AVLNode {
	if n.getLeft() == nil {
		return n
	}
	newRoot := n.getLeft()
	n.left = newRoot.getRight()
	newRoot.right = n

	newRoot.updateHeight()
	n.updateHeight()
	return newRoot
}

// バランスを整える
// 平衡係数と子のバランスによって回転や二重回転を行う

func (n *AVLNode) rebalance() *AVLNode {
	if n == nil {
		return n
	}
	n.updateHeight()

	// 平衡係数
	balanceFactor := n.left.getHeight() - n.right.getHeight()
	// 右の子の方が重い
	if balanceFactor == -2 {
		// 右の子について、左の方が重ければ二重回転が必要
		// 一旦右の子を右回転しておく
		if n.right.left.getHeight() > n.right.right.getHeight() {
			n.right = n.right.rotateRight()
		}
		return n.rotateLeft()
	} else if balanceFactor == 2 {
		if n.left.right.getHeight() > n.left.left.getHeight() {
			n.left = n.left.rotateLeft()
		}
		return n.rotateRight()
	}
	return n
}

// その部分木内でkeyを挿入
// keyがすでにあればそのノード

func (n *AVLNode) insert(key int) *AVLNode {
	if n == nil {
		return &AVLNode{key, 1, nil, nil}
	}
	if key < n.key {
		n.left = n.left.insert(key)
	} else if key > n.key {
		n.right = n.right.insert(key)
	} else {
		return n
	}
	return n.rebalance()
}

// その部分木内でkeyを削除
// keyがなければnil

func (n *AVLNode) remove(key int) *AVLNode {
	if n == nil {
		return nil
	}
	if key < n.key {
		n.left = n.left.remove(key)
	} else if key > n.key {
		n.right = n.right.remove(key)
	} else {
		if n.left != nil && n.right != nil {
			// 根を削除するときは右側から最小をさがしてきて
			// 新たな根とする
			newRoot := n.right.minNode()
			n.key = newRoot.key
			n.right = n.right.remove(newRoot.key)
		} else if n.left != nil {
			n = n.left
		} else if n.right != nil {
			n = n.right
		} else {
			n = nil
			return n
		}
	}
	return n.rebalance()
}

// その部分木内でkeyを探索
// keyがなければnil

func (n *AVLNode) search(key int) *AVLNode {
	if n == nil {
		return nil
	}
	if key < n.key {
		return n.left.search(key)
	} else if key > n.key {
		return n.right.search(key)
	} else {
		return n
	}
}

// その部分木内でkeyより大きい最小のノード
// なければnil
// keyと一致するノードがあればそれを返す

func (n *AVLNode) lowerBound(key int) *AVLNode {
	if n == nil {
		return nil
	}
	if key < n.key {
		// keyが注目ノード未満なら左の部分木を調べれば良い
		// そこになければn自身がlowerbound (左部分木のmax<keyのため)
		res := n.left.lowerBound(key)
		if res != nil {
			return res
		} else {
			return n
		}
	} else if key > n.key {
		// keyが注目モードより大きければ右を調べるのみ
		return n.right.lowerBound(key)
	} else {
		return n
	}
}

// その部分木内でkeyより小さい最大のノード
// なければnil
// keyと一致するノードがあればそれを返す

func (n *AVLNode) upperBound(key int) *AVLNode {
	if n == nil {
		return nil
	}
	// lowerBoundと逆を行う
	if key > n.key {
		res := n.right.upperBound(key)
		if res != nil {
			return res
		} else {
			return n
		}
	} else if key < n.key {
		return n.left.upperBound(key)
	} else {
		return n
	}
}

// その部分木内で最小ノード

func (n *AVLNode) minNode() *AVLNode {
	if n == nil {
		return nil
	}
	if n.left != nil {
		return n.left.minNode()
	} else {
		return n
	}
}

// その部分木内で最大ノード

func (n *AVLNode) maxNode() *AVLNode {
	if n == nil {
		return nil
	}
	if n.right != nil {
		return n.right.maxNode()
	} else {
		return n
	}
}

type AVLTree struct {
	root *AVLNode
	size int
}

func newAVLtree() *AVLTree {
	return new(AVLTree)
}

// keyを挿入
func (t *AVLTree) insert(key int) {
	if t == nil {
		return
	}
	t.root = t.root.insert(key)
	t.size++
}

// keyを削除
func (t *AVLTree) remove(key int) {
	if t == nil {
		return
	}
	t.root = t.root.remove(key)
	t.size--
}

// keyを探索 なければnil
func (t *AVLTree) search(key int) *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.search(key)
}

// keyより大きい最小のノード なければnil keyと一致するノードがあればそれを返す
func (t *AVLTree) lowerBound(key int) *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.lowerBound(key)
}

// keyより小さい最大のノード なければnil keyと一致するノードがあればそれを返す
func (t *AVLTree) upperBound(key int) *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.upperBound(key)
}

// 最大ノード なければnil
func (t *AVLTree) maxNode() *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.maxNode()
}

// 最小ノード なければnil
func (t *AVLTree) minNode() *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.minNode()
}

// そのノードの1つ後（keyが大きい）のノード なければnil
func (t *AVLTree) nextNode(n *AVLNode) *AVLNode {
	if t == nil {
		return nil
	}
	if n == nil {
		return nil
	}
	if n.right != nil {
		return n.right.minNode()
	}
	return t.lowerBound(n.key + 1)
}

// そのノードの1つ前（keyが小さい）のノード なければnil
func (t *AVLTree) prevNode(n *AVLNode) *AVLNode {
	if t == nil {
		return nil
	}
	if n == nil {
		return nil
	}
	if n.left != nil {
		return n.left.maxNode()
	}
	return t.upperBound(n.key - 1)
}

//////////////////////////////////////
// Priority Queue 優先度付きキュー ヒープ
//////////////////////////////////////

type Item struct {
	priority int
	index    int
}

func newItem(priority int, index int) *Item {
	return &Item{
		priority: priority,
		index:    index,
	}
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// 最小ヒープ
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
	*pq = append(*pq, x.(*Item))
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func newPriorityQueue(init *Item) *PriorityQueue {
	return &PriorityQueue{init}
}

// Graph

type Edge struct {
	to   int
	cost int // 辺の重み
}

type Graph struct {
	size  int
	edges [][]Edge
}

func newGraph(size int, edges [][]Edge) *Graph {
	g := Graph{
		size:  size,
		edges: edges,
	}
	return &g
}

// 「i個」の頂点を追加
func (g *Graph) addNode(i int) {
	g.size += i
	tmp := make([][]Edge, i)
	g.edges = append(g.edges, tmp...)
}

func (g *Graph) addEdge(from, to, cost int) {
	g.edges[from] = append(g.edges[from], Edge{to: to, cost: cost})
	g.edges[to] = append(g.edges[to], Edge{to: from, cost: cost}) // 有向の場合はなし
}

func (g *Graph) dijkstra(start int) []int {
	dist := newInts(g.size, INF)
	dist[start] = 0
	s := newItem(0, start)
	pq := newPriorityQueue(s)
	for pq.Len() != 0 {
		item := heap.Pop(pq).(*Item)
		v := item.index
		if item.priority > dist[v] {
			continue
		}
		for _, e := range g.edges[v] {
			tmp := dist[v] + e.cost
			if dist[e.to] > tmp {
				dist[e.to] = tmp
				heap.Push(pq, newItem(tmp, e.to))
			}
		}
	}
	return dist
}

func (g *Graph) getRadius() int {
	n := g.size
	dist := make([]int, n)
	distFrom := func(start int) {
		for i := 0; i < n; i++ {
			dist[i] = INF
		}
		dist[start] = 0
		q := make([]int, 0)
		q = append(q, start)
		for len(q) > 0 {
			v := q[0]
			if len(q) == 1 {
				q = nil
			} else {
				q = q[1:]
			}
			for _, u := range g.edges[v] {
				if dist[u.to] == INF {
					dist[u.to] = dist[v] + 1
					q = append(q, u.to)
				}
			}
		}
	}
	distFrom(0)
	max_dist, max_dist_index := -1, -1
	for i := 0; i < n; i++ {
		if max_dist < dist[i] {
			max_dist = dist[i]
			max_dist_index = i
		}
	}
	distFrom(max_dist_index)
	res := -1
	for i := 0; i < n; i++ {
		res = max(res, dist[i])
	}
	return res
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.*;

public class Main {
  private static void execute(ContestReader reader, ContestWriter out) {
    int n = reader.nextInt();
    int m = reader.nextInt();
    int[][] am = new int[m][];
    for (int i = 0; i < m; i++) {
      int k = reader.nextInt();
      am[i] = reader.nextInt(k);
    }
    int[] bs = reader.nextInt(n);
    int[] reverseBs = new int[n + 1];
    for (int i = 0; i < n; i++) {
      reverseBs[bs[i]] = i;
    }

    int[] ds = new int[n];
    for (int i = 0; i < m; i++) {
      int d = 0;
      for (int a : am[i]) {
        d = Math.max(d, reverseBs[a]);
      }
      ds[d]++;
    }
    int answer = 0;
    for (int d : ds) {
      answer += d;
      out.println(answer);
    }
  }

  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    ContestWriter out = new ContestWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}


class ContestWriter extends PrintWriter {
  ContestWriter(PrintStream printStream) {
    super(printStream);
  }

  public void printYN(boolean b) {
    println(b ? "Yes" : "No");
  }

  public void printYNList(List<Boolean> bList) {
    for (boolean b : bList) {
      printYN(b);
    }
  }

  public void printList(List<? extends Object> list) {
    for (Object object : list) {
      println(object);
    }
  }

  public void printListOneLine(List<? extends Object> list) {
    List<String> stringList = new ArrayList<>();
    for (Object object : list) {
      stringList.add(object.toString());
    }
    println(String.join(" ", stringList));
  }
}


class ContestReader {
  private static final int BUFFER_SIZE = 1024;

  private final InputStream stream;
  private final byte[] buffer;
  private int pointer;
  private int bufferLength;

  ContestReader(InputStream stream) {
    this.stream = stream;
    this.buffer = new byte[BUFFER_SIZE];
    this.pointer = 0;
    this.bufferLength = 0;
  }

  private boolean hasNextByte() {
    if (pointer < bufferLength) {
      return true;
    }

    pointer = 0;
    try {
      bufferLength = stream.read(buffer);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
    return bufferLength > 0;
  }

  private int readByte() {
    if (hasNextByte()) {
      return buffer[pointer++];
    } else {
      return -1;
    }
  }

  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }

  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[pointer])) {
      pointer++;
    }
    return hasNextByte();
  }

  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while (true) {
      int b = readByte();
      if (!isPrintableChar(b)) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }

  public String nextLine() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while (true) {
      int b = readByte();
      if (!isPrintableChar(b) && b != 0x20) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }

  public char nextChar() {
    return next().charAt(0);
  }

  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }

    int n = 0;
    boolean minus = false;

    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }

    while (true) {
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }

  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }

    long n = 0;
    boolean minus = false;

    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }

    while (true) {
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }

  public double nextDouble() {
    return Double.parseDouble(next());
  }

  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }

  public String[] nextLine(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLine();
    }
    return array;
  }

  public char[] nextChar(int n) {
    char[] array = new char[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextChar();
    }
    return array;
  }

  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }

  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }

  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }

  public char[] nextCharArray() {
    return next().toCharArray();
  }

  public String[][] next(int n, int m) {
    String[][] matrix = new String[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = next();
      }
    }
    return matrix;
  }

  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }

  public char[][] nextChar(int n, int m) {
    char[][] matrix = new char[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextChar();
      }
    }
    return matrix;
  }

  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }

  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }

  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


class Pair<T extends Comparable<T>, U extends Comparable<U>> implements Comparable<Pair<T, U>> {
  T first;
  U second;

  Pair(T first, U second) {
    this.first = first;
    this.second = second;
  }

  public int compareTo(Pair<T, U> p) {
    int tResult = first.compareTo(p.first);
    if (tResult != 0) {
      return tResult;
    }
    return second.compareTo(p.second);
  }
}


class MyAssert {
  public static void myAssert(boolean flag, String message) {
    if (!flag) {
      throw new RuntimeException(message);
    }
  }

  public static void myAssert(boolean flag) {
    myAssert(flag, "");
  }
}

JavaScript solution:
const input = require('fs').readFileSync('/dev/stdin', 'utf8')
let lines = input.split('\n')
let [N, M] = lines[0].split(' ').map(Number)

const B = lines[M + 1].split(' ').map(Number)
const map = {}

for (let i = 0; i < B.length; i++) {
  map[B[i]] = i
}

let ans = Array(N).fill(0)

for (let i = 1; i <= M; i++) {
  const A = lines[i].split(' ').map(Number)
  const K = A.shift()
  const ds = A.map((_) => map[_])
  const d = ds.reduce((a, b) => Math.max(a, b), -Infinity)
  ans[d]++
}

for (let i = 0; i < ans.length - 1; i++) {
  ans[i + 1] += ans[i]
}
console.log(ans.join('\n'))

Python solution:
N,M = map(int, input().split())
A = []
C = [0]*(N+1)
D = [0]*(N+1)
for i in range(M):
    k, *a = map(int, input().split())
    A.append(a)
B = list(map(int, input().split()))
for i in range(N):
    C[B[i]] = i + 1
for i in range(M):
    maxday = 0
    for j in range(len(A[i])):
        maxday = max(maxday, C[A[i][j]])
    D[maxday] += 1
for i in range(1,N+1):
    D[i] = D[i-1] + D[i]
    print(D[i])

Ruby solution:
n, m = gets.split.map(&:to_i)

k_a = [nil] + m.times.map { gets.split.map(&:to_i) }

b = [nil] + gets.split.map(&:to_i)
# b_after: bのindex(day)とvalue(食材)を入れ替える -> [index(食材) -> day]

b_after = [nil] + Array.new(n, nil)

(1..n).each do |day|
  food = b[day]
  b_after[food] = day
end

# b_afterを使って、k_aのindex(day)とvalue(食材)を入れ替える -> [食材のリストをdayのリストに変換] -> ソートしてlastの値がその料理を克服するday

each_day_count = [nil] + Array.new(n, 0)

(1..m).each do |ik|
  max_day = 0
  k = k_a[ik][0]
  (1..k).each do |j|
    a = k_a[ik][j]
    day = b_after[a]
    if day > max_day
      max_day = day
    end
  end
  each_day_count[max_day] += 1
end

ans = 0

(1..n).each do |i|
  ans += each_day_count[i]
  puts ans
end