結果
問題 | No.2338 Range AtCoder Query |
ユーザー | 草苺奶昔 |
提出日時 | 2024-07-30 02:43:52 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 702 ms / 4,000 ms |
コード長 | 7,402 bytes |
コンパイル時間 | 19,774 ms |
コンパイル使用メモリ | 240,080 KB |
実行使用メモリ | 30,800 KB |
最終ジャッジ日時 | 2024-07-30 02:44:32 |
合計ジャッジ時間 | 40,178 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 3 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,940 KB |
testcase_05 | AC | 3 ms
6,944 KB |
testcase_06 | AC | 4 ms
6,944 KB |
testcase_07 | AC | 5 ms
6,944 KB |
testcase_08 | AC | 6 ms
6,944 KB |
testcase_09 | AC | 5 ms
6,940 KB |
testcase_10 | AC | 5 ms
6,940 KB |
testcase_11 | AC | 567 ms
18,384 KB |
testcase_12 | AC | 487 ms
18,280 KB |
testcase_13 | AC | 506 ms
22,012 KB |
testcase_14 | AC | 498 ms
18,448 KB |
testcase_15 | AC | 573 ms
23,144 KB |
testcase_16 | AC | 685 ms
24,548 KB |
testcase_17 | AC | 653 ms
24,556 KB |
testcase_18 | AC | 641 ms
24,560 KB |
testcase_19 | AC | 674 ms
26,064 KB |
testcase_20 | AC | 642 ms
23,812 KB |
testcase_21 | AC | 669 ms
24,548 KB |
testcase_22 | AC | 649 ms
24,564 KB |
testcase_23 | AC | 689 ms
24,576 KB |
testcase_24 | AC | 659 ms
24,552 KB |
testcase_25 | AC | 677 ms
26,588 KB |
testcase_26 | AC | 256 ms
26,596 KB |
testcase_27 | AC | 258 ms
22,488 KB |
testcase_28 | AC | 249 ms
22,492 KB |
testcase_29 | AC | 571 ms
16,180 KB |
testcase_30 | AC | 702 ms
29,928 KB |
testcase_31 | AC | 580 ms
30,800 KB |
testcase_32 | AC | 378 ms
18,500 KB |
testcase_33 | AC | 554 ms
24,796 KB |
testcase_34 | AC | 523 ms
23,696 KB |
ソースコード
// 矩形区间修改单点查询(离线) package main import ( "bufio" "fmt" "os" "sort" ) func demo() { e := func() int32 { return 0 } op := func(a, b int32) int32 { return a + b } inv := func(a int32) int32 { return -a } ps := NewRectangleAddPointSumOffline(e, op, inv, false) ps.AddRectangle(0, 2, 0, 2, 1) ps.AddRectangle(1, 3, 1, 3, 2) ps.AddQuery(1, 1) ps.AddQuery(2, 2) ps.AddQuery(3, 3) res := ps.Calc() for _, v := range res { fmt.Println(v) } } func main() { yuki2338() } // No.2338 Range AtCoder Query // https://yukicoder.me/problems/no/2338 // 给定长度为n的提交记录,每一项记录形如(pid, status),表示问题编号和提交状态(AC/WA)。 // 再给定q个查询,每个查询形如(l, r),表示查询区间[l, r)内的AC数和WA数。 // !AC数:通过的题目数量(每道题最多一次AC)。 // !WA数:第一次AC之前的提交次数。 // // 对于每一个wa的记录,这个wa对查询[l,r)有贡献的条件为: // 1. l之前没有ac,r之前有ac。 func yuki2338() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, m, q int32 fmt.Fscan(in, &n, &m, &q) pids := make([]int32, n) status := make([]bool, n) for i := int32(0); i < n; i++ { fmt.Fscan(in, &pids[i]) pids[i]-- var tmp string fmt.Fscan(in, &tmp) status[i] = tmp == "AC" } groups := make([][]int32, m) for i, v := range pids { groups[v] = append(groups[v], int32(i)) } e := func() int32 { return 0 } op := func(a, b int32) int32 { return a + b } inv := func(a int32) int32 { return -a } ac := NewRectangleAddPointSumOffline(e, op, inv, true) wa := NewRectangleAddPointSumOffline(e, op, inv, true) for _, group := range groups { len_ := int32(len(group)) prev := make([]int32, len_) // pre[i]: i之前的第一个AC for i := int32(0); i < len_; i++ { prev[i] = -1 } for i, v := range group { if i > 0 { prev[i] = prev[i-1] } if status[v] { prev[i] = v } } nextAc := n for i := len_ - 1; i >= 0; i-- { index := group[i] if status[index] { // AC ac.AddRectangle(0, index+1, index+1, nextAc+1, 1) nextAc = index } else { // WA a, b := prev[i], nextAc if b == n { continue } wa.AddRectangle(a+1, index+1, b+1, n+1, 1) } } } for i := int32(0); i < q; i++ { var l, r int32 fmt.Fscan(in, &l, &r) l-- ac.AddQuery(l, r) wa.AddQuery(l, r) } res1, res2 := ac.Calc(), wa.Calc() for i := int32(0); i < q; i++ { fmt.Fprintln(out, res1[i], res2[i]) } } const INF32 int32 = 1e9 + 10 type rect[E any] struct { y, x1, x2 int32 w E } type point struct { id int32 x, y int32 } type RectangleAddPointSumOffline[E any] struct { smallX bool rects []rect[E] points []point e func() E op func(e1, e2 E) E inv func(e E) E } func NewRectangleAddPointSumOffline[E any]( e func() E, op func(e1, e2 E) E, inv func(e E) E, smallX bool, ) *RectangleAddPointSumOffline[E] { return &RectangleAddPointSumOffline[E]{smallX: smallX, e: e, op: op, inv: inv} } func (ps *RectangleAddPointSumOffline[E]) AddRectangle(xl, xr, yl, yr int32, w E) { ps.rects = append(ps.rects, rect[E]{y: yl, x1: xl, x2: xr, w: w}) ps.rects = append(ps.rects, rect[E]{y: yr, x1: xr, x2: xl, w: w}) } func (ps *RectangleAddPointSumOffline[E]) AddQuery(x, y int32) { ps.points = append(ps.points, point{id: int32(len(ps.points)), x: x, y: y}) } func (ps *RectangleAddPointSumOffline[E]) Calc() []E { n, q := int32(len(ps.rects)), int32(len(ps.points)) if n == 0 || q == 0 { res := make([]E, q) for i := int32(0); i < q; i++ { res[i] = ps.e() } return res } rects, points := ps.rects, ps.points // compress x nx := int32(0) if !ps.smallX { sort.Slice(points, func(i, j int) bool { return points[i].x < points[j].x }) keyX := make([]int32, 0, q) for i := int32(0); i < q; i++ { x := points[i].x if len(keyX) == 0 || keyX[len(keyX)-1] != x { keyX = append(keyX, x) } points[i].x = int32(len(keyX) - 1) } for i := int32(0); i < n; i++ { rects[i].x1 = lowerBound32(keyX, rects[i].x1) rects[i].x2 = lowerBound32(keyX, rects[i].x2) } nx = int32(len(keyX)) } else { mx := INF32 for i := int32(0); i < q; i++ { if tmp := points[i].x; tmp < mx { mx = tmp } } for i := int32(0); i < q; i++ { points[i].x -= mx if tmp := points[i].x + 1; tmp > nx { nx = tmp } } for i := int32(0); i < n; i++ { rects[i].x1 = clamp32(rects[i].x1-mx, 0, nx) rects[i].x2 = clamp32(rects[i].x2-mx, 0, nx) } } sort.Slice(points, func(i, j int) bool { return points[i].y < points[j].y }) sort.Slice(rects, func(i, j int) bool { return rects[i].y < rects[j].y }) bit := newFenwickTree(ps.e, ps.op, ps.inv) bit.Build(nx, func(i int32) E { return ps.e() }) res := make([]E, q) for i := range res { res[i] = ps.e() } j := int32(0) for _, point := range points { q, x, y := point.id, point.x, point.y for j < n && rects[j].y <= y { rect := rects[j] j++ bit.Update(rect.x1, rect.w) bit.Update(rect.x2, ps.inv(rect.w)) } res[q] = bit.QueryPrefix(x + 1) } return res } type fenwickTree[E any] struct { n int32 total E data []E e func() E op func(e1, e2 E) E inv func(e E) E } func newFenwickTree[E any](e func() E, op func(e1, e2 E) E, inv func(e E) E) *fenwickTree[E] { return &fenwickTree[E]{e: e, op: op, inv: inv} } func (fw *fenwickTree[E]) Build(n int32, f func(i int32) E) { data := make([]E, n) for i := int32(0); i < n; i++ { data[i] = f(i) } for i := int32(1); i <= n; i++ { if j := i + (i & -i); j <= n { data[j-1] = fw.op(data[i-1], data[j-1]) } } fw.n = n fw.data = data fw.total = fw.QueryPrefix(n) } func (fw *fenwickTree[E]) QueryAll() E { return fw.total } // [0, end) func (fw *fenwickTree[E]) QueryPrefix(end int32) E { if end > fw.n { end = fw.n } res := fw.e() for ; end > 0; end &= end - 1 { res = fw.op(res, fw.data[end-1]) } return res } // [start, end) func (fw *fenwickTree[E]) QueryRange(start, end int32) E { if start < 0 { start = 0 } if end > fw.n { end = fw.n } if start > end { return fw.e() } if start == 0 { return fw.QueryPrefix(end) } pos, neg := fw.e(), fw.e() for end > start { pos = fw.op(pos, fw.data[end-1]) end &= end - 1 } for start > end { neg = fw.op(neg, fw.data[start-1]) start &= start - 1 } return fw.op(pos, fw.inv(neg)) } // 要求op满足交换律(commute). func (fw *fenwickTree[E]) Update(i int32, x E) { fw.total = fw.op(fw.total, x) for i++; i <= fw.n; i += i & -i { fw.data[i-1] = fw.op(fw.data[i-1], x) } } func (fw *fenwickTree[E]) GetAll() []E { res := make([]E, fw.n) for i := int32(0); i < fw.n; i++ { res[i] = fw.QueryRange(i, i+1) } return res } func lowerBound32(nums []int32, x int32) int32 { left, right := int32(0), int32(len(nums)-1) for left <= right { mid := (left + right) >> 1 if nums[mid] < x { left = mid + 1 } else { right = mid - 1 } } return left } func clamp32(x, l, r int32) int32 { if x < l { return l } if x > r { return r } return x } 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 } func min32(a, b int32) int32 { if a < b { return a } return b } func max32(a, b int32) int32 { if a > b { return a } return b }