[2020 NPSC高中組初賽]兔田建設
出處: 2020 NPSC網際網路程式設計大賽高中組初賽pF
こんぺここんぺこー
西元 20xx 年，有個知名的競賽程式 vtuber 團體，致力於提升自己在各大 online judge 的 Elo rating，史稱 EloLive。
其中，又有擅長構造題的一幫人，被稱做「兔田建設」（Usada Construction）。
今天，兔田建設收到一個委託，要在一片草原上構造一間南瓜屋。這片草原非常特殊，可以被想像成一個整數序列，其中每個數值代表着一個位置草的多寡。
他們希望這間寬度爲 \(k\) 的南瓜屋被建造在一個區間 \([l, r]\) 中。除此之外，他們希望南瓜屋建造的地方恰好有 \(c\) 塊草地的數值在 \(v\) 以下，如此這間南瓜屋的生草值才會恰到好處。不過，因爲兔田社長總是出爾反爾的（而且有時候會分不清楚東南西北），所以他們決定了一條清單，清單上有 \(q\) 種可能的方案 \((v_i, l_i, r_i, c_i)\)。而他們想要知道，對於每一種方案，是否能夠建構出符合條件的南瓜屋。
正式地說，給定一個長度爲 \(n\) 的整數序列 \(a_1, a_2, \ldots, a_n\) 以及一個固定寬度 \(k\)，你需要回答 \(q\) 筆詢問，每一筆詢問 \((v_i, l_i, r_i, c_i)\) 代表是否能在序列的 \([l_i, r_i]\) 區間內找到一個長度爲 \(k\) 的連續區間，使其恰好有 \(c_i\) 個不大於 \(v_i\) 的值。
輸入格式
輸入的第一行包含兩個整數 \(n\) 和 \(k\)，表示草原的長度以及南瓜屋的寬度。
第二行有 \(n\) 個整數 \(a_1, a_2, \ldots, a_n\)，表示代表草原的整數序列。
第三行有一個整數 \(q\)，表示詢問的次數。
接下來有 \(q\) 行，每一行表示一筆詢問。每筆詢問包含四個整數 \((v_i, l_i, r_i, c_i)\)，詢問是否能在 \([l_i, r_i]\) 區間內建造出恰好蓋住 \(c_i\) 塊不大於 \(v_i\) 的草地的南瓜屋。
- \(1 \le n, q, k \le 10^6\)
- \(1 \le a_i \le 10^9\)
- \(1 \le v_i \le n\)
- \(1 \le l_i \le r_i \le n\)
- \(0 \le c_i \le k\)
輸出格式
對於每筆詢問，請輸出 \(1\) 或 \(0\)，分別代表能或不能建造出符合條件的南瓜屋。
範例輸入1
3 1
7 7 2
2
4 3 3 0
2 1 3 0範例輸出1
0
1範例輸入2
4 2
12 9 7 11
2
17 2 2 2
5 1 2 1範例輸出2
0
0範例輸入3
10 3
4 17 19 20 22 24 26 11 16 13
5
15 6 10 3
30 1 7 0
22 8 9 3
23 3 10 2
18 1 8 1範例輸出3
0
0
0
1
1
评论
望學長把這題時限改成3.0s 記憶體改成256M orzzzzz
Sorry 現在才看到～
鑑於當年比賽沒有像以往都會公布各題的時間和記憶體限制，本題已嘗試放寬時間和記憶體要求～