Cordillera Oriental là một dãy núi thuộc dãy Andes trải dài qua Bolivia. Dãy núi gồm một dãy \(N\) đỉnh núi, được đánh số từ \(0\) đến \(N - 1\). Độ cao của đỉnh thứ \(i\) (\(0 \le i < N\)) là \(H[i]\), là một số nguyên nằm trong đoạn từ \(1\) đến \(N - 1\).

Với hai đỉnh bất kỳ \(i\) và \(j\) thỏa mãn \(0 \le i < j < N\), khoảng cách giữa chúng được định nghĩa là \(d(i, j) = j - i\).

Theo các truyền thuyết Inca cổ xưa, một bộ ba đỉnh núi được gọi là huyền thoại nếu nó có tính chất đặc biệt sau: ba độ cao của ba đỉnh núi trùng khớp với ba khoảng cách đôi một giữa chúng (không kể thứ tự).

Một cách hình thức, bộ ba chỉ số \((i, j, k)\) là huyền thoại nếu:

• \(0 \le i < j < k < N\), và
• ba độ cao \((H[i], H[j], H[k])\) trùng khớp với ba khoảng cách đôi một \((d(i, j), d(i, k), d(j, k))\) không kể thứ tự. Ví dụ, với các chỉ số \(0, 1, 2\) thì các khoảng cách đôi một là \((1, 2, 1)\), nên các bộ độ cao \((H[0], H[1], H[2]) = (1, 1, 2)\), \((H[0], H[1], H[2]) = (1, 2, 1)\), và \((H[0], H[1], H[2]) = (2, 1, 1)\) đều khớp, nhưng bộ độ cao \((H[0], H[1], H[2]) = (1, 2, 2)\) thì không khớp.

Bài toán này gồm hai phần, mỗi subtask thuộc về Phần I hoặc Phần II. Bạn có thể giải các subtask theo thứ tự bất kỳ. Đặc biệt, bạn không bắt buộc phải hoàn thành toàn bộ Phần I trước khi làm Phần II.

Phần I

Cho mô tả của dãy núi, nhiệm vụ của bạn là đếm số bộ ba huyền thoại.

Phần II

Nhiệm vụ của bạn là dựng các dãy núi có nhiều bộ ba huyền thoại. Phần này gồm \(6\) subtask chỉ nộp output với chấm điểm từng phần.

Trong mỗi subtask, bạn được cho hai số nguyên dương \(M\) và \(K\), và bạn cần dựng một dãy núi có nhiều nhất \(M\) đỉnh. Nếu lời giải của bạn chứa ít nhất \(K\) bộ ba huyền thoại, bạn sẽ nhận được điểm tối đa cho subtask đó. Ngược lại, điểm của bạn sẽ tỉ lệ thuận với số bộ ba huyền thoại trong lời giải.

Lưu ý lời giải của bạn phải tạo thành một dãy núi hợp lệ. Cụ thể, giả sử lời giải có \(N\) đỉnh (\(N\) phải thỏa mãn \(3 \le N \le M\)). Khi đó, độ cao của đỉnh thứ \(i\) (\(0 \le i < N\)), ký hiệu là \(H[i]\), phải là một số nguyên nằm trong đoạn từ \(1\) đến \(N - 1\).

Chi tiết cài đặt

Bạn cần cài đặt hai hàm sau trong file triples.h:

Phần I: Bạn cần cài đặt hàm

long long count_triples(std::vector<int> H)

• \(H\): mảng độ dài \(N\), biểu diễn độ cao của các đỉnh núi.
• Hàm này được gọi đúng một lần cho mỗi test.
• Hàm cần trả về một số nguyên \(T\), là số bộ ba huyền thoại trong dãy núi.

Phần II: Bạn có thể nộp lời giải bằng một trong hai cách: nộp file output hoặc cài đặt hàm sau:

std::vector<int> construct_range(int M, int K)

• \(M\): số đỉnh tối đa.
• \(K\): số bộ ba huyền thoại mong muốn.
• Hàm này được gọi đúng một lần cho mỗi subtask.
• Hàm cần trả về một mảng \(H\) độ dài \(N\), biểu diễn độ cao các đỉnh núi.

Để nộp bằng file output, hãy tạo và nộp một file văn bản theo định dạng:

N
H[0] H[1] ... H[N-1]

Ràng buộc

• \(3 \le N \le 200\,000\)
• \(1 \le H[i] \le N - 1\) với mọi \(i\) thỏa \(0 \le i < N\).

Phân nhóm

Phần I có tổng cộng \(70\) điểm:

• Subtask 1 (\(8\) điểm): \(N \le 100\).
• Subtask 2 (\(6\) điểm): \(H[i] \le 10\) với mọi \(i\) thỏa \(0 \le i < N\).
• Subtask 3 (\(10\) điểm): \(N \le 2000\).
• Subtask 4 (\(11\) điểm): Các độ cao không giảm. Tức là \(H[i-1] \le H[i]\) với mọi \(i\) thỏa \(1 \le i < N\).
• Subtask 5 (\(16\) điểm): \(N \le 50\,000\).
• Subtask 6 (\(19\) điểm): Không có ràng buộc bổ sung.

Phần II có tổng cộng \(30\) điểm. Trong mỗi subtask, các giá trị \(M\) và \(K\) là cố định và được cho trong bảng sau:

Ví dụ

Xét lời gọi sau:

count_triples([4, 1, 4, 3, 2, 6, 1])

Có \(3\) bộ ba huyền thoại trong dãy núi:

• Với \((i, j, k) = (1, 3, 4)\), các độ cao \((1, 3, 2)\) khớp với các khoảng cách đôi một \((2, 3, 1)\).
• Với \((i, j, k) = (2, 3, 6)\), các độ cao \((4, 3, 1)\) khớp với các khoảng cách đôi một \((1, 4, 3)\).
• Với \((i, j, k) = (3, 4, 6)\), các độ cao \((3, 2, 1)\) khớp với các khoảng cách đôi một \((1, 3, 2)\).

Do đó, hàm cần trả về \(3\).

Lưu ý rằng các chỉ số \((0, 2, 4)\) không tạo thành bộ ba huyền thoại, vì các độ cao \((4, 4, 2)\) không khớp với các khoảng cách đôi một \((2, 4, 2)\).

Trình chấm mẫu dùng chung cho Phần I và Phần II, phân biệt qua dòng đầu tiên của input.

Định dạng input cho Phần I:

1
N
H[0] H[1] ... H[N-1]

Định dạng output cho Phần I:

T

Định dạng input cho Phần II:

2
M K

Định dạng output cho Phần II:

N
H[0] H[1] ... H[N-1]

Lưu ý rằng output của trình chấm mẫu khớp với định dạng yêu cầu cho file output ở Phần II.

1
7
4 1 4 3 2 6 1

3

2
20 30

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1

Chấm điểm

Với mỗi subtask của Phần II, nếu lời giải của bạn không tạo thành một dãy núi hợp lệ, điểm sẽ là \(0\) (báo Output isn't correct trên CMS).

Ngược lại, gọi \(T\) là số bộ ba huyền thoại trong lời giải của bạn. Khi đó, điểm cho subtask đó là: