結果

問題 No.2927 Reverse Polish Equation
コンテスト
ユーザー ID 21712
提出日時 2025-03-20 00:17:29
言語 Go
(1.23.4)
結果
AC  
実行時間 199 ms / 2,000 ms
コード長 3,368 bytes
コンパイル時間 11,791 ms
コンパイル使用メモリ 252,316 KB
実行使用メモリ 14,668 KB
最終ジャッジ日時 2025-03-20 00:17:48
合計ジャッジ時間 17,632 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "os"
import bf "bufio"

func main() {
	rd := bf.NewReader(Stdin)
	var q int
	var y int64
	Fscan(rd, &q, &y)
	a := make([]Node, 0, q)
	for i := 0; i < q; i++ {
		var s string
		Fscan(rd, &s)
		switch s {
			case "+":
				p := len(a)-1
				a[p-1] = opSum(a[p-1], a[p])
				a = a[:p]
			case "max":
				p := len(a)-1
				a[p-1] = opMax(a[p-1], a[p])
				a = a[:p]
			case "min":
				p := len(a)-1
				a[p-1] = opMin(a[p-1], a[p])
				a = a[:p]
			case "X":
				a = append(a, &Value{1, 0})
			default:
				var c int64
				Sscan(s, &c)
				a = append(a, &Value{0, c})
		}
	}
	var lower, upper int64 = -1, y+1
	for lower+1<upper {
		middle := (lower+upper)/2
		value := a[0].Calc(middle)
		if value < y {
			lower = middle
		} else {
			upper = middle
		}
	}
	if a[0].Calc(upper) == y {
		Println(upper)
	} else {
		Println(-1)
	}
}

type Node interface {
	Calc(x int64) int64
}

type Value struct {
	k, c int64
}
func (v *Value) Calc(x int64) int64 {
	return v.k*x+v.c
}
func (v *Value) Add(other *Value) {
	v.k += other.k
	v.c += other.c
}
func (v *Value) LessThan(other *Value) bool {
	return v.k <= other.k && v.c <= other.c
}
func (v *Value) GreaterThan(other *Value) bool {
	return v.k >= other.k && v.c >= other.c
}

type OpSum struct {
	value Value
	ns []Node
}
func (op *OpSum) Calc(x int64) int64 {
	sum := op.value.Calc(x)
	for _, n := range op.ns {
		sum += n.Calc(x)
	}
	return sum
}
func (op *OpSum) Append(ns ...Node) {
	for _, n := range ns {
		switch w := n.(type) {
			case *Value:
				op.value.Add(w)
			case *OpSum:
				op.value.Add(&w.value)
				op.ns = append(op.ns, w.ns...)
			default:
				op.ns = append(op.ns, n)
		}
	}
}

type OpMin struct {
	ns []Node
}
func (op *OpMin) Calc(x int64) int64 {
	res := op.ns[0].Calc(x)
	for _, n := range op.ns[1:] {
		tmp := n.Calc(x)
		if tmp < res {
			res = tmp
		}
	}
	return res
}

type OpMax struct {
	ns []Node
}
func (op *OpMax) Calc(x int64) int64 {
	res := op.ns[0].Calc(x)
	for _, n := range op.ns[1:] {
		tmp := n.Calc(x)
		if tmp > res {
			res = tmp
		}
	}
	return res
}

func opSum(n1, n2 Node) Node {
	if v1, v1ok := n1.(*Value); v1ok {
		if v2, v2ok := n2.(*Value); v2ok {
			v1.Add(v2)
			return v1
		}
	}
	if s1, s1ok := n1.(*OpSum); s1ok {
		s1.Append(n2)
		return s1
	}
	if s2, s2ok := n2.(*OpSum); s2ok {
		s2.Append(n1)
		return s2
	}
	op := new(OpSum)
	op.Append(n1, n2)
	return op
}

func opMin(n1, n2 Node) Node {
	if v1, v1ok := n1.(*Value); v1ok {
		if v2, v2ok := n2.(*Value); v2ok {
			if v1.LessThan(v2) {
				return v1
			} else if v2.LessThan(v1) {
				return v2
			}
		}
	}
	if m1, m1ok := n1.(*OpMin); m1ok {
		if m2, m2ok := n2.(*OpMin); m2ok {
			m1.ns = append(m1.ns, m2.ns...)
		} else {
			m1.ns = append(m1.ns, n2)
		}
		return m1
	}
	if m2, m2ok := n2.(*OpMin); m2ok {
		m2.ns = append(m2.ns, n1)
		return m2
	}
	return &OpMin{ []Node{n1, n2} }
}

func opMax(n1, n2 Node) Node {
	if v1, v1ok := n1.(*Value); v1ok {
		if v2, v2ok := n2.(*Value); v2ok {
			if v1.GreaterThan(v2) {
				return v1
			} else if v2.GreaterThan(v1) {
				return v2
			}
		}
	}
	if m1, m1ok := n1.(*OpMax); m1ok {
		if m2, m2ok := n2.(*OpMax); m2ok {
			m1.ns = append(m1.ns, m2.ns...)
		} else {
			m1.ns = append(m1.ns, n2)
		}
		return m1
	}
	if m2, m2ok := n2.(*OpMax); m2ok {
		m2.ns = append(m2.ns, n1)
		return m2
	}
	return &OpMax{ []Node{n1, n2} }
}
0