結果

問題 No.1826 Fruits Collecting
ユーザー 草苺奶昔
提出日時 2023-03-03 16:44:20
言語 Go
(1.23.4)
結果
AC  
実行時間 364 ms / 2,000 ms
コード長 2,493 bytes
コンパイル時間 11,490 ms
コンパイル使用メモリ 238,336 KB
実行使用メモリ 21,940 KB
最終ジャッジ日時 2024-09-17 22:04:49
合計ジャッジ時間 18,837 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)
	goods := make([][3]int, n) // time, pos, score
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &goods[i][0], &goods[i][1], &goods[i][2])
	}

	txs := make([][3]int, 0, n)
	set := map[int]struct{}{0: {}} // start pos
	for i := 0; i < n; i++ {
		t, x, s := goods[i][0], goods[i][1], goods[i][2]
		if abs(x) <= t { // reachable
			txs = append(txs, [3]int{t + x, t - x, s})
			set[t-x] = struct{}{}
		}
	}

	sort.Slice(txs, func(i, j int) bool {
		if txs[i][0] == txs[j][0] {
			return txs[i][1] < txs[j][1]
		}
		return txs[i][0] < txs[j][0]
	})
	sorted := make([]int, 0, len(set))
	for k := range set {
		sorted = append(sorted, k)
	}
	sort.Ints(sorted)
	mp := make(map[int]int, len(sorted))
	for i, v := range sorted {
		mp[v] = i
	}

	seg := NewFenwickTreePrefix(len(sorted))
	seg.Set(0, 0)
	for i := 0; i < len(txs); i++ {
		x, s := txs[i][1], txs[i][2]
		pos := mp[x]
		curMax := seg.Query(pos+1) + s
		seg.Set(pos, curMax)
	}
	fmt.Fprintln(out, seg.Query(len(sorted)))

}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

type S = int

const INF int = 1e18

func (*FenwickTreePrefix) e() S        { return -INF }
func (*FenwickTreePrefix) op(a, b S) S { return max(a, b) }
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

type FenwickTreePrefix struct {
	n    int
	data []S
}

func NewFenwickTreePrefix(n int) *FenwickTreePrefix {
	res := &FenwickTreePrefix{n, make([]S, n+1)}
	for i := 0; i < n+1; i++ {
		res.data[i] = res.e()
	}
	return res
}

func NewFenwickTreePrefixWithSlice(nums []S) *FenwickTreePrefix {
	n := len(nums)
	res := &FenwickTreePrefix{n, make([]S, n+1)}
	for i := n; i > 0; i-- {
		res.data[i] = res.op(res.data[i], nums[i-1])
		if p := i + (i & -i); p <= n {
			res.data[p] = res.op(res.data[p], res.data[i])
		}
	}
	return res
}

// 单点更新index处的元素.
// 0 <= index < n
func (f *FenwickTreePrefix) Set(index int, value S) {
	for index++; index <= f.n; index += index & -index {
		f.data[index] = f.op(f.data[index], value)
	}
}

// 查询前缀区间 [0,right) 的值.
// 0 <= right <= n
func (f *FenwickTreePrefix) Query(right int) S {
	res := f.e()
	if right > f.n {
		right = f.n
	}
	for ; right > 0; right -= right & -right {
		res = f.op(res, f.data[right])
	}
	return res
}
0