Thi thử TS10 2024 - Ngày 1

Khu vực xung quanh sân khấu được trang trí bởi bóng đèn đánh số từ 1 đến \(n\). Để đêm trao giải hấp dẫn thì các bóng đèn này sẽ được thay đổi trạng thái theo quy luật: bóng đang bật sẽ tắt, bóng đang tắt sẽ bật. Một bóng đèn sẽ thay đổi trạng thái ở thời điểm \(t\) nếu số thứ tự của bóng đèn đó chia hết cho \(t\). Tại thời điểm 0, tất cả các bóng đèn đều tắt và chương trình bắt đầu tại thời điểm 1. Sau thời điểm \(n\) thì tất cả các bóng đèn sẽ giữ nguyên trạng thái và không thay đổi nữa.

Yêu cầu: Hãy tính xem sau thời điểm \(n\) thì từ bóng đèn thứ \(a\) đến bóng đèn thứ \(b\) có bao nhiêu bóng đèn đang bật.

Input

• Đọc từ tệp văn bản 24TFL1A.inp:
  • Một dòng duy nhất gồm ba số nguyên dương \(n, a, b\) (\(1 \le a \le b \le n \le 10^{15}\)).

Output

• In ra tệp văn bản 24TFL1A.out:
  • Một số duy nhất là kết quả bài toán.

Ràng buộc bổ sung

• \(50\%\) số điểm có \(n \le 1000\).
• \(30\%\) số điểm khác có \(n \le 10^5\).
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.

Example

4 1 4

2

0    -    -    -    -
1    +    +    +    +
2    +    -    +    -
3    +    -    -    -
4    +    -    -    +

Đan và Phúc là hai bạn trẻ rất tài năng trong lĩnh vực Tin học. Một hôm, Phúc đố Đan một bài toán sau:

• Cho hai số nguyên dương \(A, B\), đếm số cặp số \((x, y)\) sao cho \(1 \le x \le A\), \(1 \le y \le B\) và \(x + y\) chia hết cho 10 (ngày sinh của Đan).

Đan có thể giải quyết bài toán rất nhanh chóng với \(A, B\) đủ nhỏ, nhưng với các trường hợp \(A, B\) lớn thì Đan cần sự giúp đỡ của các bạn.

Input

• Đọc từ tệp văn bản 24TFL1B.inp:
  • Một dòng duy nhất gồm hai số nguyên dương \(A, B\) (\(1 \le A, B \le 10^{18}\)).

Output

• Ghi vào tệp văn bản 24TFL1B.out:
  • Một dòng duy nhất gồm số lượng cặp số \((x, y)\) thỏa mãn.

Example

7 7

4

15 10

13

Scoring

• 40% số điểm có \(A, B \le 5000\).
• 20% số điểm khác có \(A, B \le 10^9\).
• 20% số điểm khác có \(A \le 10^9, B \le 10^{18}\).
• 10% số điểm khác có \(A, B \le 10^{12}\).
• 10% số điểm còn lại không có giới hạn gì thêm.

Trung vị của một dãy số nguyên \(a_1, a_2, \dots, a_n\) được sắp xếp tăng dần là \(a_{\lfloor \frac{n+1}{2} \rfloor}\), với \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\). Nếu dãy \(a\) chưa được sắp xếp tăng dần, ta sắp xếp lại dãy rồi tìm trung vị.

Một dãy \(b_1, b_2, \dots, b_n\) được gọi là hoán vị của một dãy \(a_1, a_2, \dots, a_n\) khi và chỉ khi tồn tại một cách sắp xếp các phần tử của dãy sao cho thu được dãy \(b\).

Yêu cầu

Cho một hoán vị \(a_1, a_2, \dots, a_n\) của dãy \(1, 2, 3, \dots, n\). Với mỗi số nguyên \(v\) (\(1 \le v \le n\)), hãy đếm số đoạn con liên tiếp của dãy nhận \(v\) làm trung vị, hay nói cách khác, hãy đếm số lượng cặp số \((l, r)\) sao cho \(1 \le l \le r \le n\) và \(v\) là trung vị của \(a_l, a_{l+1}, \dots, a_r\).

Input

• Dữ liệu nhập vào từ file 24TFL1C.inp:
  • Dòng đầu tiên gồm một số nguyên dương \(n\) (\(1 \le n \le 5000\)).
  • Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)).
  • Dữ liệu đầu vào đảm bảo các giá trị đôi một phân biệt.

Output

• Ghi ra file 24TFL1C.out:
  • Gồm \(n\) số nguyên trên cùng một dòng, số nguyên dương thứ \(v\) là số cặp \((l, r)\) sao cho \(a_l, a_{l+1}, \dots, a_r\) nhận \(v\) làm trung vị.

Ràng buộc bổ sung

• \(8\%\) số điểm có \(n \le 9\).
• \(8\%\) số điểm khác có \(n \le 60\).
• \(12\%\) số điểm khác có \(n \le 100\).
• \(12\%\) số điểm khác có \(n \le 300\).
• \(16\%\) số điểm khác có \(n \le 500\).
• \(20\%\) số điểm khác có \(n \le 2000\).
• \(24\%\) số điểm còn lại không có giới hạn gì thêm.

Example

5
1 2 3 4 5

2 4 5 3 1

4
4 2 3 1

1 5 2 2

Ở TLEOJ Cup năm nay, các thành viên của câu lạc bộ TLE tổ chức trao thưởng cho những thí sinh có thành tích xuất sắc bằng một trò chơi nhỏ. Trò chơi diễn ra trên một lưới gồm \(n\) hàng và \(m\) cột. Ô ở hàng \(i\), cột \(j\) được ký hiệu là \((i,j)\). Có \(k\) ô chứa quà; ô thứ \(t\) nằm tại \((x_t,y_t)\) và có \(v_t\) phần quà.

Người chơi bắt đầu ở một ô bất kỳ trên hàng thứ nhất và thực hiện đúng \(n\) bước. Ở mỗi bước:

• Nếu ô hiện tại có quà, người chơi nhận tất cả quà trong ô đó.
• Nếu đang ở ô \((i,j)\) với \(i<n\), người chơi có thể đi đến một trong các ô

miễn là ô đích nằm trong lưới.

• Nếu \(i=n\), trò chơi kết thúc.

Hãy tìm số phần quà tối đa người chơi có thể nhận.

Xem các hình minh họa đường đi của ví dụ trong đề PDF chính thức.

Input

• Dòng đầu chứa bốn số nguyên không âm \(n,m,k,d\) (\(1 \le n,m \le 10^9\), \(0 \le k \le \min(nm,2\cdot10^5)\), \(0 \le d < m\)).
• \(k\) dòng tiếp theo, dòng thứ \(t\) chứa ba số nguyên dương \(x_t,y_t,v_t\), cho biết ô \((x_t,y_t)\) có \(v_t\) phần quà (\(1 \le x_t \le n\), \(1 \le y_t \le m\), \(1 \le v_t \le 10^9\)).
• Các vị trí \((x_t,y_t)\) đôi một phân biệt.

Output

• In ra một số nguyên là số phần quà tối đa có thể nhận.

Example

2 4 2 2
2 1 1
2 2 2

2

4 5 4 1
3 2 1
4 1 1
1 5 2
2 2 1

3

1 3 2 0
1 2 1000000000
1 1 1000000000

1000000000

Scoring

• \(5\%\) số điểm: \(k \le 2\).
• \(5\%\) số điểm: \(d=0\).
• \(10\%\) số điểm: \(n,m \le 15\) và \(d=1\).
• \(10\%\) số điểm: \(n,m \le 200\).
• \(10\%\) số điểm: \(n,m \le 1000\).
• \(10\%\) số điểm: \(n,m \le 5000\).
• \(15\%\) số điểm: \(k \le 5000\).
• \(15\%\) số điểm: \(d=1\) và \(v_i=1\).
• \(10\%\) số điểm: \(d=1\).
• \(10\%\) số điểm: không có ràng buộc gì thêm.