結果
問題 | No.1826 Fruits Collecting |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-03 16:39:30 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 440 ms / 2,000 ms |
コード長 | 4,005 bytes |
コンパイル時間 | 12,342 ms |
コンパイル使用メモリ | 221,292 KB |
実行使用メモリ | 25,892 KB |
最終ジャッジ日時 | 2023-10-18 01:04:18 |
合計ジャッジ時間 | 23,325 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 3 ms
4,348 KB |
testcase_02 | AC | 3 ms
4,348 KB |
testcase_03 | AC | 5 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 171 ms
9,232 KB |
testcase_06 | AC | 285 ms
14,860 KB |
testcase_07 | AC | 204 ms
11,268 KB |
testcase_08 | AC | 23 ms
5,616 KB |
testcase_09 | AC | 277 ms
16,088 KB |
testcase_10 | AC | 187 ms
11,040 KB |
testcase_11 | AC | 181 ms
9,452 KB |
testcase_12 | AC | 73 ms
6,472 KB |
testcase_13 | AC | 37 ms
5,640 KB |
testcase_14 | AC | 59 ms
6,456 KB |
testcase_15 | AC | 434 ms
25,012 KB |
testcase_16 | AC | 439 ms
25,892 KB |
testcase_17 | AC | 437 ms
23,976 KB |
testcase_18 | AC | 431 ms
24,992 KB |
testcase_19 | AC | 437 ms
24,652 KB |
testcase_20 | AC | 440 ms
25,352 KB |
testcase_21 | AC | 429 ms
25,184 KB |
testcase_22 | AC | 430 ms
25,020 KB |
testcase_23 | AC | 437 ms
25,000 KB |
testcase_24 | AC | 432 ms
24,948 KB |
testcase_25 | AC | 1 ms
4,348 KB |
testcase_26 | AC | 2 ms
4,348 KB |
testcase_27 | AC | 2 ms
4,348 KB |
testcase_28 | AC | 1 ms
4,348 KB |
testcase_29 | AC | 1 ms
4,348 KB |
testcase_30 | AC | 86 ms
7,964 KB |
testcase_31 | AC | 172 ms
9,964 KB |
testcase_32 | AC | 107 ms
7,448 KB |
testcase_33 | AC | 369 ms
24,792 KB |
testcase_34 | AC | 313 ms
22,540 KB |
testcase_35 | AC | 72 ms
6,996 KB |
testcase_36 | AC | 365 ms
24,776 KB |
testcase_37 | AC | 259 ms
19,092 KB |
testcase_38 | AC | 176 ms
14,492 KB |
testcase_39 | AC | 254 ms
15,392 KB |
testcase_40 | AC | 324 ms
20,148 KB |
testcase_41 | AC | 69 ms
6,188 KB |
testcase_42 | AC | 11 ms
4,348 KB |
testcase_43 | AC | 1 ms
4,348 KB |
testcase_44 | AC | 1 ms
4,348 KB |
testcase_45 | AC | 1 ms
4,348 KB |
ソースコード
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 := NewSegmentTree(make([]E, len(sorted)+10)) for i := 0; i < len(txs); i++ { x, s := txs[i][1], txs[i][2] pos := mp[x] curMax := seg.Query(0, pos+1) + s seg.Set(pos, curMax) } fmt.Fprintln(out, seg.QueryAll()) } func abs(x int) int { if x < 0 { return -x } return x } const INF int = 4e18 // PointSetRangeMax type E = int func (*SegmentTree) e() E { return -INF } func (*SegmentTree) op(a, b E) E { return max(a, b) } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } type SegmentTree struct { n, size int seg []E } func NewSegmentTree(leaves []E) *SegmentTree { res := &SegmentTree{} n := len(leaves) size := 1 for size < n { size <<= 1 } seg := make([]E, size<<1) for i := 0; i < n; i++ { seg[i+size] = leaves[i] } for i := size - 1; i > 0; i-- { seg[i] = res.op(seg[i<<1], seg[i<<1|1]) } res.n = n res.size = size res.seg = seg return res } func (st *SegmentTree) Get(index int) E { if index < 0 || index >= st.n { return st.e() } return st.seg[index+st.size] } func (st *SegmentTree) Set(index int, value E) { if index < 0 || index >= st.n { return } index += st.size st.seg[index] = value for index >>= 1; index > 0; index >>= 1 { st.seg[index] = st.op(st.seg[index<<1], st.seg[index<<1|1]) } } // [start, end) func (st *SegmentTree) Query(start, end int) E { if start < 0 { start = 0 } if end > st.n { end = st.n } if start >= end { return st.e() } leftRes, rightRes := st.e(), st.e() start += st.size end += st.size for start < end { if start&1 == 1 { leftRes = st.op(leftRes, st.seg[start]) start++ } if end&1 == 1 { end-- rightRes = st.op(st.seg[end], rightRes) } start >>= 1 end >>= 1 } return st.op(leftRes, rightRes) } func (st *SegmentTree) QueryAll() E { return st.seg[1] } // 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MaxRight(left int, predicate func(E) bool) int { if left == st.n { return st.n } left += st.size res := st.e() for { for left&1 == 0 { left >>= 1 } if !predicate(st.op(res, st.seg[left])) { for left < st.size { left <<= 1 if predicate(st.op(res, st.seg[left])) { res = st.op(res, st.seg[left]) left++ } } return left - st.size } res = st.op(res, st.seg[left]) left++ if (left & -left) == left { break } } return st.n } // 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MinLeft(right int, predicate func(E) bool) int { if right == 0 { return 0 } right += st.size res := st.e() for { right-- for right > 1 && right&1 == 1 { right >>= 1 } if !predicate(st.op(st.seg[right], res)) { for right < st.size { right = right<<1 | 1 if predicate(st.op(st.seg[right], res)) { res = st.op(st.seg[right], res) right-- } } return right + 1 - st.size } res = st.op(st.seg[right], res) if right&-right == right { break } } return 0 }