So Sánh Chuỗi Con Cuộn
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề bài
Cho chuỗi $S$ có độ dài $N$ và $Q$ truy vấn. Mỗi truy vấn gồm bốn số nguyên $l_1, r_1, l_2, r_2$, hãy so sánh theo thứ tự từ điển hai chuỗi con $S[l_1..r_1]$ và $S[l_2..r_2]$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
- Dòng thứ hai chứa chuỗi $S$.
- $Q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $l_1, r_1, l_2, r_2$ ($1$-indexed).
Dữ liệu ra
- Với mỗi truy vấn, in ra:
-1nếu $S[l_1..r_1] < S[l_2..r_2]$0nếu $S[l_1..r_1] = S[l_2..r_2]$1nếu $S[l_1..r_1] > S[l_2..r_2]$
Ví dụ
| Input | Output |
|---|---|
| 6 3\nabcabc\n1 3 4 6\n1 2 2 3\n1 3 1 3 | 0\n-1\n0 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le Q \le 10^5$
- $1 \le l_1 \le r_1 \le N$, $1 \le l_2 \le r_2 \le N$
- Chuỗi chỉ chứa ký tự in thường từ
ađếnz.
Community Discussion