Chọn đội tuyển HSGQG Hải Phòng 2025 (Ngày 1 + Ngày 2)

Nguồn: Previously reviewed PDF copied without content changes

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. RECT

Cho $n$ điểm trên mặt phẳng tọa độ. Điểm thứ $i$ có tọa độ là $(x i, y i)$ (các điểm có thể trùng nhau). Hải vẽ $m$ hình chữ nhật lên mặt phẳng này, các hình chữ nhật có cạnh song song với một trong hai trục tọa độ. Hình chữ nhật thứ $j$ có tọa độ góc trái dưới là $(u j1, v j1)$ và tọa độ góc phải trên $(u j2, v j2)$ .

Yêu cầu: Với mỗi hình chữ nhật, hãy xác định số điểm nằm trên các cạnh của hình chữ nhật.

Input

Dòng đầu tiên chứa số nguyên dương $n$ ( $n \leq 3 \times 105$ );

$n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $x i, y i$ là hoành độ và tung độ của điểm thứ $i$ ( $1 \leq x i, y i \leq 109$ );

Dòng kế tiếp chứa số nguyên dương $m$ ( $m \leq 105$ );

$m$ dòng tiếp theo, dòng thứ $j$ chứa 4 số nguyên dương $u j1, v j1, u j2, v j2$ ( $1 \leq u j1 \leq u j2 \leq 109$ ; $1 \leq v j1 \leq v j2 \leq 109$ ) mô tả hình chữ nhật thứ $j$ có tọa độ góc trái dưới là $(u j1, v j1)$ và tọa độ góc phải trên là $(u j2, v j2)$ .

Output

Ghi ra $m$ dòng, dòng thứ $j$ ghi một số nguyên là số lượng điểm nằm trên các cạnh của hình chữ nhật thứ $j$ ( $j = 1, 2, \dots, m$ ).

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. GRAPH

Trên bản đồ thành phố HP có $n$ địa điểm (đánh số từ 1 đến $n$ ) và $m$ con đường hai chiều (đánh số từ 1 đến $m$ ), con đường $i$ ( $1 \leq i \leq m$ ) nối giữa hai địa điểm $u i$ và $v i$ ( $1 \leq u i, v i \leq n$ ; $u i \neq v i$ ) có độ nguy hiểm là $p i$ và tiêu tốn nhiên liệu $w i$ .

Hải muốn di chuyển từ địa điểm 1 đến địa điểm $n$ sao cho độ nguy hiểm lớn nhất là nhỏ nhất và trong số những cách di chuyển có độ nguy hiểm lớn nhất là nhỏ nhất đó thì chọn cách đi tốn ít nhiên liệu nhất.

Yêu cầu: Tìm giá trị nhỏ nhất của độ nguy hiểm lớn nhất và lượng nhiên liệu ít nhất tương ứng.

Input

Dòng đầu tiên gồm hai số nguyên dương $n, m$ ( $1 \leq n \leq 2 \times 105$ , $1 \leq m \leq 3 \times 105$ );

$m$ dòng sau, mỗi dòng gồm bốn số nguyên dương $u i, v i, p i, w i$ mô tả một con đường nối giữa hai địa điểm $u i$ và $v i$ ; có độ nguy hiểm là $p i$ ( $1 \leq p i \leq 1018$ ) và tiêu tốn nhiên liệu $w i$ ( $1 \leq w i \leq 5 \times 1012$ ).

Output

Ghi ra hai số nguyên theo thứ tự là giá trị nhỏ nhất của độ nguy hiểm lớn nhất khi di chuyển từ địa điểm 1 đến địa điểm $n$ và lượng nhiên liệu ít nhất trong số tất cả các cách di chuyển có độ nguy hiểm lớn nhất là nhỏ nhất.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. DOMINO

Hải có $n$ quân domino xếp thành một hàng ngang, đánh số từ trái sang phải từ 1 đến $n$ . Một mặt của domino thứ $i$ ghi số nguyên dương $a i$ , mặt còn lại ghi số nguyên dương $b i$ . Ban đầu, xếp các quân domino sao cho mặt ghi $a i$ quay lên trên, mặt ghi $b i$ quay xuống dưới.

Hải thực hiện thao tác sau $k$ lần: Cho một số nguyên dương $T$ , lật tất cả những quân domino có số được ghi ở mặt trên nhỏ hơn hoặc bằng $T$ .

Yêu cầu: Sau khi thực hiện đủ $k$ lần, hãy tính tổng $n$ số được ghi trên mặt đang quay lên trên.

Input

Dòng đầu tiên gồm hai số nguyên dương $n, k$ ( $1 \leq n, k \leq 2 \times 105$ );

$n$ dòng sau, dòng thứ $i$ chứa hai số nguyên dương $a i, b i$ ( $1 \leq a i, b i \leq 109$ ) là hai số được ghi trên quân domino thứ $i$ . Ban đầu, mặt $a i$ được quay lên trên, còn mặt $b i$ quay xuống dưới;

$k$ dòng sau, dòng thứ $i$ gồm một số nguyên dương $T i$ ( $1 \leq T i \leq 109$ ) là giá trị được chọn cho thao tác thứ $i$ .

Output

Ghi ra một số nguyên dương duy nhất là tổng $n$ số được ghi trên mặt quay lên trên của $n$ quân domino.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. SUBSEQ

Cho hai dãy số nguyên $A = (a 1, a 2, \dots, a n)$ và $B = (b 1, b 2, \dots, b n)$ . Ta định nghĩa giá trị của đoạn con $(i, j)$ với $1 \leq i \leq j \leq n$ bằng biểu thức: $a i \times b j + a i+1 \times b j-1 + \dots + a j \times b i = \sum k=0 j-i a i+k \times b j-k$

Ví dụ: Nếu $A = (7, 2, 1, 4, 6)$ và $B = (4, 5, 0, -2, 3)$ thì giá trị đoạn con $(2, 4)$ bằng: $2 \times (-2) + 1 \times 0 + 4 \times 5 = 16$

Yêu cầu: Tính giá trị lớn nhất của một đoạn con.

Input

Dòng đầu tiên chứa số nguyên dương $n$ ( $1 \leq n \leq 5000$ );

Dòng thứ hai chứa $n$ số nguyên $a 1, a 2, \dots, a n$ ( $|a i | \leq 106$ );

Dòng thứ ba chứa $n$ số nguyên $b 1, b 2, \dots, b n$ ( $|b i | \leq 106$ ). Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là giá trị lớn nhất của đoạn con tìm được.

Sample Input 1

5
7 2 1 4 6
4 5 0 -2 3

Sample Output 1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. TREE

Cho đồ thị vô hướng liên thông có $n$ đỉnh (đánh số từ 1 đến $n$ ) và $n - 1$ cạnh. Mỗi cạnh có trọng số là số nguyên dương $C$ . Trong số $n$ đỉnh thì có đúng $k$ đỉnh được đánh dấu.

Yêu cầu: Với mỗi đỉnh $i$ ( $1 \leq i \leq n$ ), hãy tìm đường đi ngắn nhất xuất phát từ đỉnh $i$ và đi qua tất cả $k$ đỉnh được đánh dấu.

Input

Dòng đầu tiên chứa hai số nguyên dương $n, k$ ( $1 < n \leq 2 \times 105, 1 \leq k \leq n$ );

$n - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $A, B, C$ ( $1 \leq A, B \leq n, 1 \leq C \leq 106$ ) thể hiện có một cạnh nối đỉnh $A$ với đỉnh $B$ có trọng số bằng $C$ ;

$k$ dòng cuối cùng, mỗi dòng chứa chỉ số của một đỉnh được đánh dấu. Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra $n$ dòng, dòng thứ $i$ là độ dài đường đi ngắn nhất xuất phát từ đỉnh $i$ ( $1 \leq i \leq n$ ) và đi qua tất cả $k$ đỉnh được đánh dấu.

Sample Input 1

Sample Output 1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. MUL

Hải được Thầy giáo cho dãy $a$ gồm $n$ số nguyên dương $a 1, a 2, \dots, a n$ . Ban đầu, $a 1 = a 2 = \dots = a n = 1$ . Hải thực hiện $q$ thao tác dạng $[L, R, k, x]$ , mỗi thao tác nhân các phần tử ở các vị trí $L + t \times k$ (với $0 \leq t \leq ⌊ R-L k ⌋$ ) lên $x$ lần.

Hãy in ra dãy $a$ sau khi thực hiện đủ $q$ thao tác. Vì các giá trị $a i$ ( $1 \leq i \leq n$ ) có thể rất lớn nên chỉ cần tính theo phần dư của phép chia $a i$ cho $109 + 7$ .

Input

Dòng đầu tiên gồm hai số nguyên dương $n, q$ ( $1 \leq n \leq 5 \times 104, 1 \leq q \leq 2 \times 105$ ) lần lượt là độ dài dãy $a$ và số lượng thao tác;

$q$ dòng sau, mỗi dòng gồm bốn số nguyên dương $L, R, k, x$ ( $1 \leq L \leq R \leq n, 1 \leq k \leq n, 1 \leq x \leq 109$ ) mô tả một thao tác. Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra trên một dòng gồm $n$ số nguyên dương là dãy $a$ sau $q$ thao tác, các số cách nhau bởi dấu cách.

Sample Input 1

5 2
1 4 2 4
1 5 2 3

Sample Output 1

12 1 12 1 3

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Cấu trúc đề và tiến độ