結果
問題 | No.1300 Sum of Inversions |
ユーザー | sgsw |
提出日時 | 2021-08-14 03:22:00 |
言語 | Go (1.22.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,233 bytes |
コンパイル時間 | 11,387 ms |
コンパイル使用メモリ | 222,936 KB |
実行使用メモリ | 88,804 KB |
最終ジャッジ日時 | 2024-04-15 01:00:03 |
合計ジャッジ時間 | 48,872 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1,178 ms
74,468 KB |
testcase_04 | AC | 1,102 ms
70,016 KB |
testcase_05 | AC | 829 ms
49,280 KB |
testcase_06 | AC | 1,306 ms
78,080 KB |
testcase_07 | AC | 1,259 ms
70,912 KB |
testcase_08 | AC | 1,392 ms
75,848 KB |
testcase_09 | AC | 1,343 ms
73,728 KB |
testcase_10 | AC | 670 ms
39,168 KB |
testcase_11 | AC | 653 ms
40,320 KB |
testcase_12 | AC | 1,196 ms
73,728 KB |
testcase_13 | AC | 1,163 ms
74,496 KB |
testcase_14 | AC | 1,497 ms
80,512 KB |
testcase_15 | AC | 1,420 ms
78,208 KB |
testcase_16 | AC | 1,188 ms
75,904 KB |
testcase_17 | AC | 666 ms
39,552 KB |
testcase_18 | AC | 737 ms
42,240 KB |
testcase_19 | AC | 1,041 ms
72,704 KB |
testcase_20 | AC | 1,065 ms
76,544 KB |
testcase_21 | AC | 1,057 ms
75,264 KB |
testcase_22 | AC | 863 ms
43,008 KB |
testcase_23 | AC | 1,276 ms
76,928 KB |
testcase_24 | AC | 883 ms
46,292 KB |
testcase_25 | AC | 735 ms
44,544 KB |
testcase_26 | AC | 695 ms
40,704 KB |
testcase_27 | AC | 796 ms
46,336 KB |
testcase_28 | AC | 1,461 ms
75,880 KB |
testcase_29 | AC | 1,021 ms
77,568 KB |
testcase_30 | AC | 1,330 ms
77,696 KB |
testcase_31 | AC | 836 ms
48,128 KB |
testcase_32 | AC | 892 ms
44,544 KB |
testcase_33 | AC | 826 ms
75,904 KB |
testcase_34 | AC | 838 ms
77,312 KB |
testcase_35 | AC | 880 ms
83,568 KB |
testcase_36 | WA | - |
ソースコード
package main import ( "bufio" "fmt" "os" "sort" "strconv" "reflect" ) var wg = bufio.NewScanner(os.Stdin) const ( inf = int(1e18) initialBufSize = int(1e6) maxBufSize = int(1e6) mod = 998244353 ) var buf []byte = make([]byte, initialBufSize) func init() { wg.Split(bufio.ScanWords) wg.Buffer(buf, maxBufSize) } func nextInt() int { wg.Scan() i, e := strconv.Atoi(wg.Text()) if e != nil { panic(e) } return i } /* Monoid-Structure should be decleared some-where else. -> op(Monoid,Monoid)Monoid & ide()Monoid is required. */ type Monoid interface { Get() interface{} Op(Monoid) Monoid Ide() Monoid } type SegTree struct { monoid_type Monoid op func(Monoid) Monoid /* op */ e func() Monoid /*identity*/ d []Monoid _d []Monoid n int /* size*/ log int size int } func Gen(monoid Monoid, n int) (SegTree, bool) { seg := SegTree{monoid_type: monoid, op: monoid.Op, e: monoid.Ide, d: []Monoid{}, _d: []Monoid{}, n: 0, log: 0, size: 0} collect := true switch n > 0 { case true: seg.d = make([]Monoid, n) for i := range seg.d { seg.d[i] = seg.e() } default: collect = false return seg, collect } seg.n = len(seg.d) for ord := 0; (1 << ord) < seg.n; { ord++ seg.log = ord } seg.size = 1 << seg.log seg._d = make([]Monoid, 2*seg.size) for i := range seg._d { seg._d[i] = seg.e() } for i := 0; i < seg.n; i++ { seg._d[seg.size+i] = seg.d[i] } for i := seg.size - 1; i > 0; i-- { seg._update(i) } return seg, collect } func SliceGen(seg SegTree, array []Monoid) bool { ok := true if len(array) != seg.n { ok = false return ok } for _, v := range array { if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) { ok = false return ok } } for i, v := range array { seg.Set(i, v) } for i := seg.size - 1; i > 0; i-- { seg._update(i) } return ok } func (seg SegTree) _update(k int) { seg._d[k] = seg._d[2*k].Op(seg._d[2*k+1]) } func (seg SegTree) Set(p int, x Monoid) { //a[p] -> x p += seg.size seg._d[p] = x for i := 1; i <= seg.log; i++ { seg._update(p >> i) } } func (seg SegTree) Get(p int) Monoid { // a[p] return seg._d[p+seg.size] } func (seg SegTree) OverWrite(p int, f func(Monoid) Monoid) { p += seg.size m := seg._d[p] seg._d[p] = f(m) for i := 1; i <= seg.log; i++ { seg._update(p >> i) } } func (seg SegTree) Prod(l, r int) Monoid { //op(a[l..r)) sml := seg.e() smr := seg.e() l += seg.size r += seg.size for l < r { if l&1 == 1 { sml = sml.Op(seg._d[l]) l++ } if r&1 == 1 { r-- smr = seg._d[r].Op(smr) } l >>= 1 r >>= 1 } return sml.Op(smr) } func (seg SegTree) All_prod() Monoid { return seg._d[1] } type numbers struct { val, idx int } type monoid struct { val, cnt int } func (x monoid) Get() interface{} { return x } func (x monoid) Op(y Monoid) Monoid { return monoid{x.val + y.(monoid).val, x.cnt + y.(monoid).cnt} } func (x monoid) Ide() Monoid { return monoid{0, 0} } func main() { n := nextInt() a := make([]numbers, n) for i := 0; i < n; i++ { x := nextInt() a[i] = numbers{val: x, idx: i} } //left sort.Slice(a, func(i, j int) bool { if a[i].val > a[j].val { return true } else if a[i].val < a[j].val { return false } else { return a[i].idx > a[j].idx } }) seg, _ := Gen(monoid{}, n) left := make([]monoid, n) for _, v := range a { left[v.idx] = seg.Prod(0, v.idx).(monoid) seg.Set(v.idx, monoid{v.val, 1}) } //right sort.Slice(a, func(i, j int) bool { if a[i].val < a[j].val { return true } else if a[i].val > a[j].val { return false } else { return a[i].idx < a[j].idx } }) seg1, _ := Gen(monoid{}, n) right := make([]monoid, n) for _, v := range a { right[v.idx] = seg1.Prod(v.idx+1, n).(monoid) seg1.Set(v.idx, monoid{v.val, 1}) } ans := 0 for i := 0; i < n; i++ { if left[a[i].idx].cnt*right[a[i].idx].cnt > 0 { lval, lcnt := left[a[i].idx].val, left[a[i].idx].cnt rval, rcnt := right[a[i].idx].val, right[a[i].idx].cnt middle := a[i].val ans += lval*rcnt%mod + rval*lcnt%mod + middle*lcnt%mod*rcnt%mod ans %= mod } } fmt.Printf("%d\n", ans) }