HSG9 Hà Nội 2025 - Dây đèn

Xem dạng PDF

Gửi bài giải

Điểm: 17,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Người đăng:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Để trang trí Tết, Nam treo một dây đèn gồm ~N~ bóng đèn, được đánh số từ 1 đến ~N~, từ trái sang phải. Mỗi bóng đèn khi bật sẽ có hai màu vàng hoặc đỏ. Dây đèn được nhúng một mã lệnh cho phép nhận một số tự nhiên ~X~. Khi đó, màu của bóng đèn thứ ~X~ và các bóng đèn cách bóng đèn thứ ~X~ không quá ~K~ bóng đèn sẽ đều đổi từ vàng thành đỏ hoặc ngược lại.

Ban đầu các bóng đèn đều có màu vàng. Để dây đèn trông đẹp mắt, Nam đã lập trình để điều khiển màu của các bóng đèn. Chương trình của Nam có ~M~ dòng lệnh, mỗi dòng lệnh tương ứng với một lần gọi mã lệnh của dây đèn. Vì số lượng bóng đèn quá lớn, sau khi lập trình xong, Nam muốn kiểm tra ngẫu nhiên màu một số bóng đèn xem có đúng như ý tưởng ban đầu không.

Yêu cầu: Cho các số tự nhiên ~X~ là tham số của ~M~ dòng lệnh trong chương trình của Nam. Hãy lập trình để trả lời ~Q~ câu hỏi tương ứng với các lần kiểm tra của Nam. Biết rằng mỗi câu hỏi chứa một số nguyên dương ~P~ để xác định xem bóng đèn thứ ~P~ trong dây đèn có màu vàng hay đỏ.

Input

  • Dòng đầu tiên gồm bốn số nguyên dương lần lượt là ~N, M, Q, K~ (~1 \le N \le 10^9; 1 \le M \le 10^5; 1 \le Q \le 10^5; 0 \le K \le N~);
  • Dòng thứ hai gồm ~M~ số nguyên dương ~X_i~ mô tả tham số của lệnh thứ ~i~ (~1 \le X_i \le N~);
  • Dòng thứ ba gồm ~Q~ số nguyên dương ~P_i~ mô tả câu hỏi thứ ~i~ (~1 \le P_i \le N~).

Output

Gồm ~Q~ dòng, dòng thứ ~i~ là câu trả lời cho câu hỏi thứ ~i~. Nếu bóng đèn tại vị trí ~P_i~ đang có màu vàng thì ghi ra ký tự "V", ngược lại ghi ra ký tự "D".

Sample Input 1

7 2 4 1
3 5
2 7 4 5

Sample Output 1

D
V
V
D

Giải thích:

  • Sau lần gọi mã lệnh thứ nhất (X = 3, K = 1), các bóng đèn trong khoảng [2, 4] đổi màu sang Đỏ. Trạng thái: ~V, D, D, D, V, V, V~.
  • Sau lần gọi mã lệnh thứ hai (X = 5, K = 1), các bóng đèn trong khoảng [4, 6] đổi màu. Bóng đèn 4 (Đỏ thành Vàng), bóng đèn 5 và 6 (Vàng thành Đỏ). Trạng thái: ~V, D, D, V, D, D, V~.

Ràng buộc

  • Có 60% số test ứng với 60% số điểm của bài thỏa mãn: ~N, M, Q \le 10^3~;
  • 20% số test khác ứng với 20% số điểm của bài thỏa mãn: ~N, M \le 10^5~;
  • 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -1
    thinhphamminh274  đã bình luận lúc 10, Tháng 11, 2026, 5:31

    PHÂN TÍCH BÀI TOÁN VÀ GIẢI THUẬT: DÂY ĐÈN

    1. Phân tích bài toán

    • Đề bài:
      • Có một dây đèn gồm $N$ bóng đèn, đánh số từ $1$ đến $N$. Ban đầu tất cả các bóng đèn đều có màu vàng (V).
      • Có $M$ lần gọi mã lệnh. Mỗi lần gọi với tham số $X$ sẽ làm thay đổi màu của bóng đèn thứ $X$ và tất cả các bóng đèn nằm trong đoạn từ $\max(1, X - K)$ đến $\min(N, X + K)$ (tức là cách bóng $X$ không quá $K$ đơn vị).
      • Có $Q$ câu hỏi kiểm tra. Mỗi câu hỏi cho một vị trí $P$, yêu cầu xác định màu hiện tại của bóng đèn thứ $P$ là vàng (V) hay đỏ (D).
    • Tính chất quan trọng:
      • Mỗi lần một bóng đèn chịu tác động từ lệnh $X$, màu của nó sẽ bị đảo ngược một lần (từ vàng thành đỏ, hoặc từ đỏ thành vàng).
      • Ban đầu mọi bóng đèn đều là màu vàng (tương ứng với số lần lật trạng thái ban đầu là $0$ - số chẵn).
      • Sau tất cả $M$ lệnh, tổng số lần mà một bóng đèn thứ $P$ bị tác động chính bằng số lượng tham số $X$ thỏa mãn điều kiện: $$X - K \le P \le X + K \iff P - K \le X \le P + K$$
      • Nếu tổng số lần tác động này là chẵn, màu cuối cùng của bóng đèn là vàng (V).
      • Nếu tổng số lần tác động này là lẻ, màu cuối cùng của bóng đèn là đỏ (D).

    2. Giải thuật chi tiết

    Bước 1: Đọc dữ liệu và lưu trữ
    • Đọc các giá trị $N, M, Q, K$.
    • Đọc $M$ giá trị tham số $X_i$ vào mảng $a$.
    Bước 2: Sắp xếp mảng tham số
    • Sắp xếp mảng $a$ từ phần tử thứ $1$ đến $M$ theo thứ tự tăng dần (sort(a + 1, a + m + 1)).
    • Việc sắp xếp này giúp ta có thể sử dụng tìm kiếm nhị phân để đếm số lượng lệnh $X$ nằm trong đoạn $[P - K, P + K]$ một cách cực kỳ nhanh chóng.
    Bước 3: Xử lý các truy vấn bằng Tìm kiếm nhị phân
    • Với mỗi câu hỏi kiểm tra vị trí $P$:
      • Ta cần đếm số lượng phần tử $X$ trong mảng $a$ thỏa mãn: $P - K \le X \le P + K$.
      • Sử dụng lower_bound(a + 1, a + m + 1, P - K) để tìm vị trí đầu tiên có giá trị lớn hơn hoặc bằng $P - K$.
      • Sử dụng upper_bound(a + 1, a + m + 1, P + K) để tìm vị trí đầu tiên có giá trị lớn hơn $P + K$.
      • Số lượng lệnh tác động đến bóng $P$ là res = r - l.
    • Kiểm tra tính chẵn lẻ của res:
      • Nếu res % 2 == 0: In ra ký tự V (vàng).
      • Ngược lại (res % 2 != 0): In ra ký tự D (đỏ).

    3. Đánh giá độ phức tạp

    • Độ phức tạp sắp xếp: $O(M \log M)$ để sắp xếp mảng các tham số lệnh.
    • Độ phức tạp truy vấn: Mỗi truy vấn sử dụng lower_bound và upper_bound mất $O(\log M)$. Với $Q$ truy vấn, tổng thời gian xử lý truy vấn là $O(Q \log M)$.
    • Tổng độ phức tạp thời gian: $O((M + Q) \log M)$, hoàn toàn tối ưu và chạy mượt mà trong giới hạn $M, Q \le 10^5$ với giới hạn thời gian 1.0 giây.
      #include <bits/stdc++.h>
      #define ll long long
      #define Sonic() cin.tie(NULL)->syncwithstdio(0)
      #define el '\n'
      #define fi first
      #define se second
      #define str string
      #define NAME "DAYDEN"
      using namespace std;
      
      
      

      void inp(){ freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout); }

      ll a[100005];

      int main() { Sonic(); //inp(); ll n,m,q,k;cin>>n>>m>>q>>k; for(ll i=1;i<=m;i++)cin>>a[i]; sort(a+1,a+m+1); while(q--){ ll p;cin>>p; ll l=lowerbound(a+1,a+m+1,p-k)-a; ll r=upperbound(a+1,a+m+1,p+k)-a; ll res=r-l; if(res%2==0)cout<<'V'<<el; else cout<<'D'<<el; } return 0; }