結果

問題 No.2735 Demarcation
ユーザー kusirakusirakusirakusira
提出日時 2024-04-09 23:16:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 514 ms / 1,500 ms
コード長 2,444 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 261,312 KB
最終ジャッジ日時 2024-04-19 19:39:09
合計ジャッジ時間 9,526 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
52,608 KB
testcase_01 AC 33 ms
52,744 KB
testcase_02 AC 33 ms
52,400 KB
testcase_03 AC 32 ms
52,864 KB
testcase_04 AC 258 ms
212,208 KB
testcase_05 AC 176 ms
89,644 KB
testcase_06 AC 284 ms
201,864 KB
testcase_07 AC 482 ms
236,252 KB
testcase_08 AC 435 ms
229,888 KB
testcase_09 AC 244 ms
128,616 KB
testcase_10 AC 277 ms
165,772 KB
testcase_11 AC 129 ms
109,752 KB
testcase_12 AC 149 ms
85,320 KB
testcase_13 AC 237 ms
95,872 KB
testcase_14 AC 476 ms
204,864 KB
testcase_15 AC 309 ms
89,728 KB
testcase_16 AC 310 ms
202,400 KB
testcase_17 AC 376 ms
154,628 KB
testcase_18 AC 225 ms
109,568 KB
testcase_19 AC 418 ms
235,680 KB
testcase_20 AC 514 ms
226,932 KB
testcase_21 AC 280 ms
198,040 KB
testcase_22 AC 248 ms
242,040 KB
testcase_23 AC 145 ms
112,664 KB
testcase_24 AC 189 ms
164,256 KB
testcase_25 AC 238 ms
190,680 KB
testcase_26 AC 204 ms
177,724 KB
testcase_27 AC 234 ms
185,364 KB
testcase_28 AC 313 ms
261,304 KB
testcase_29 AC 318 ms
261,312 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
X = list(map(int, input().split()))
for i in range(N):
    X[i] -= 1
diff_sum = [0 for _ in range(N)]
for i in range(N - 1):
    if X[i] != X[i + 1]:
        diff_sum[i + 1] = diff_sum[i]
    else:
        diff_sum[i + 1] = diff_sum[i] + 1

kinds = [0 for _ in range(N)]

Q = int(input())
for _ in range(Q):
    l, r, S = map(int, input().split())
    l -= 1
    r -= 1
    if r - l >= 90:
        diffs = diff_sum[r] - diff_sum[l]
        if diffs >= 60:
            print(0)
        else:
            if S >= (1 << diffs):
                print(1)
            else:
                print(0)
    else:
        vec = [0 for _ in range(r - l + 1)]
        for j in range(l, r + 1):
            vec[j - l] = X[j]
        len_vec = len(vec)

        ans = [0 for _ in range(len_vec + 2)]
        ok = 0
        ng = len_vec + 2

        while ng - ok > 1:
            mid = (ok + ng) // 2
            prev_idx = [-1 for _ in range(len_vec + 1)]
            now_kind = 0

            left = 0
            right = 0

            while True:
                if now_kind <= mid:
                    if right == len_vec:
                        prev_idx[right] = left
                        break
                    else:
                        prev_idx[right] = left
                        if kinds[vec[right]] == 0:
                            now_kind += 1
                        kinds[vec[right]] += 1
                        right += 1
                else:
                    kinds[vec[left]] -= 1
                    if kinds[vec[left]] == 0:
                        now_kind -= 1
                    left += 1
            dp = [0 for _ in range(len_vec + 1)]
            dp_sum = [0 for _ in range(len_vec + 1)]
            dp[0] = 1
            dp_sum[0] = 1
            infin = False

            for j in range(1, len_vec + 1):
                sum_val = dp_sum[j - 1]
                if prev_idx[j] > 0:
                    sum_val -= dp_sum[prev_idx[j] - 1]
                if sum_val > S:
                    infin = True
                    break
                dp[j] = sum_val
                dp_sum[j] = dp[j] + dp_sum[j - 1]
            if infin:
                ng = mid
            else:
                ok = mid
                ans[mid] = dp[len_vec]

            for j in range(len_vec):
                kinds[vec[j]] = 0

        if ok >= len_vec:
            print(-1)
        else:
            print(ok)
0