結果
問題 | No.905 Sorted? |
ユーザー | brthyyjp |
提出日時 | 2020-06-30 06:47:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 453 ms / 2,000 ms |
コード長 | 2,391 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 94,976 KB |
最終ジャッジ日時 | 2024-07-19 17:07:32 |
合計ジャッジ時間 | 6,919 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
52,608 KB |
testcase_01 | AC | 47 ms
53,504 KB |
testcase_02 | AC | 43 ms
52,480 KB |
testcase_03 | AC | 43 ms
52,608 KB |
testcase_04 | AC | 44 ms
52,480 KB |
testcase_05 | AC | 94 ms
75,904 KB |
testcase_06 | AC | 67 ms
66,304 KB |
testcase_07 | AC | 125 ms
77,312 KB |
testcase_08 | AC | 426 ms
85,248 KB |
testcase_09 | AC | 341 ms
83,712 KB |
testcase_10 | AC | 405 ms
94,592 KB |
testcase_11 | AC | 453 ms
91,264 KB |
testcase_12 | AC | 447 ms
89,984 KB |
testcase_13 | AC | 431 ms
94,336 KB |
testcase_14 | AC | 433 ms
94,976 KB |
testcase_15 | AC | 232 ms
94,464 KB |
testcase_16 | AC | 261 ms
94,848 KB |
testcase_17 | AC | 254 ms
94,464 KB |
testcase_18 | AC | 284 ms
94,208 KB |
testcase_19 | AC | 43 ms
52,352 KB |
testcase_20 | AC | 43 ms
52,480 KB |
testcase_21 | AC | 43 ms
52,736 KB |
testcase_22 | AC | 42 ms
52,480 KB |
ソースコード
import syssys.setrecursionlimit(10**7)input = sys.stdin.buffer.readlinen = int(input())A = list(map(int, input().split()))if n == 1:q = int(input())for i in range(q):l, r = map(int, input().split())print(1, 1)exit()B = [0]*(n-1)for i in range(n-1):B[i] = A[i+1]-A[i]def min_(x, y):if x <= y:return xelse:return ydef mininit(init_val):# set_valfor i in range(n-1):sgmin[i+num-1] = init_val[i]# builtfor i in range(num-2, -1, -1):sgmin[i] = min_(sgmin[2*i+1], sgmin[2*i+2])def minupdate(k, x):k += num - 1sgmin[k] = xwhile k:k = (k-1)//2sgmin[k] = min_(sgmin[2*k+1], sgmin[2*k+2])def minquery(p, q):if q <= p:return ide_ele_minp += num - 1q += num - 2res = ide_ele_minwhile q-p>1:if p&1 == 0:res = min_(res, sgmin[p])if q&1 == 1:res = min_(res, sgmin[q])q -= 1p = p//2q = (q-1)//2if p == q:res = min_(res, sgmin[p])else:res = min_(min_(res, sgmin[p]), sgmin[q])return resdef max_(x, y):if x >= y:return xelse:return ydef maxinit(init_val):# set_valfor i in range(n-1):sgmax[i+num-1] = init_val[i]# builtfor i in range(num-2, -1, -1):sgmax[i] = max_(sgmax[2*i+1], sgmax[2*i+2])def maxupdate(k, x):k += num - 1sgmax[k] = xwhile k:k = (k-1)//2sgmax[k] = max_(sgmax[2*k+1], sgmax[2*k+2])def maxquery(p, q):if q <= p:return ide_ele_maxp += num - 1q += num - 2res = ide_ele_maxwhile q-p>1:if p&1 == 0:res = max_(res, sgmax[p])if q&1 == 1:res = max_(res, sgmax[q])q -= 1p = p//2q = (q-1)//2if p == q:res = max_(res, sgmax[p])else:res = max_(max_(res, sgmax[p]), sgmax[q])return res# identity elementide_ele_min = 10**18ide_ele_max = -10**18num = 2**(n-2).bit_length()sgmin = [ide_ele_min]*2*numsgmax = [ide_ele_max]*2*nummininit(B)maxinit(B)q = int(input())for i in range(q):l, r = map(int, input().split())ans = [0, 0]if minquery(l, r) >= 0:ans[0] = 1if maxquery(l, r) <= 0:ans[1] = 1print(*ans)