GCJ/2008/1C/C/main.go

package main

import (
	"bufio"
	"fmt"
	"os"
)

// MOD ...
const MOD = 1000000007

func countIncreasing(scanner *bufio.Scanner) []int {
	caseCnt := ReadInt(scanner)
	answer := make([]int, caseCnt)
	for cid := 0; cid < caseCnt; cid++ {
		println("Case", cid+1, "/", caseCnt)
		params := ReadInts(scanner)
		n, m, X, Y, Z := params[0], params[1], params[2], params[3], params[4]
		A := make([]int, m)
		limits := make([]int, n)
		for i := 0; i < n; i++ {
			if i < m {
				A[i] = ReadInt(scanner)
			}
			limits[i] = A[i%m]
			A[i%m] = (X*A[i%m] + Y*(i+1)) % Z
		} // To generate input array 'limits'
		st := NewSegmentTree(limits)
		dp := make([]int, n+1)
		dp[0] = 1
		for i := 1; i <= n; i++ {
			dp[i]++
			// *********************************
			// *     Segment tree solution     *
			// *********************************
			for j := st.NextGreater(limits[i-1], i) + 1; j != 0; j = st.NextGreater(limits[i-1], j) + 1 {
				dp[j] += dp[i]
				dp[j] %= MOD
			}
			// *********************************
			// *       Original solution       *
			// *********************************
			// for j := i + 1; j <= n; j++ { // It is too slow to search between i+1 and n for big case
			// 	if limits[i-1] < limits[j-1] {
			// 		dp[j] += dp[i]
			// 		dp[j] %= MOD
			// 	}
			// }
			// *********************************
			// Both are to slow for solving the big problem set.
		}
		for i := 1; i <= n; i++ {
			answer[cid] += dp[i]
		}
		answer[cid] %= MOD
	}
	return answer
}

func main() {
	inputFiles := []string{"C-small-practice.in", "C-large-practice.in", "test.in"}
	outputFiles := []string{"result-small.out", "result-large.out", "test.out"}
	const (
		small = iota
		large
		test
	)

	fileType := small

	fin, _ := os.Open(inputFiles[fileType])
	defer fin.Close()

	scanner := bufio.NewScanner(fin)
	answer := countIncreasing(scanner)

	fout, _ := os.Create(outputFiles[fileType])
	defer fout.Close()

	for i, v := range answer {
		s := fmt.Sprintf("Case #%d: %d\n", i+1, v)
		fout.WriteString(s)
	}
}