結果

問題 No.905 Sorted?
ユーザー るこーそー
提出日時 2025-03-03 00:40:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 410 ms / 2,000 ms
コード長 2,587 bytes
コンパイル時間 562 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 98,936 KB
最終ジャッジ日時 2025-03-03 00:40:57
合計ジャッジ時間 6,404 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self,op,e,v):
        self.n=len(v)
        self.op=op
        self.e=e
        self.size=1<<(self.n-1).bit_length()
        self.node=[self.e]*(2*self.size)
        for i in range(self.n):
            self.node[self.size+i]=v[i]
        for i in range(self.size-1,0,-1):
            self.node[i]=self.op(self.node[i*2],self.node[i*2+1])
    
    def set(self,k,x):
        k+=self.size
        self.node[k]=x
        while k>1:
            k//=2
            self.node[k]=self.op(self.node[2*k],self.node[2*k+1])
    
    def prod_rec(self,a,b,k=1,l=0,r=-1):
        if r<0:r=self.size
        if (r<=a or b<=l):return self.e 
        if (a<=l and r<=b):return self.node[k]
        vl=self.prod_rec(a,b,2*k,l,(l+r)//2)
        vr=self.prod_rec(a,b,2*k+1,(l+r)//2,r)
        return self.op(vl,vr)
    
    def prod(self,l,r):
        l,r=l+self.size,r+self.size
        vl,vr=self.e,self.e
        while l<r:
            if l&1:
                vl=self.op(vl,self.node[l])
                l+=1
            if r&1:
                r-=1
                vr=self.op(self.node[r],vr)
            l>>=1
            r>>=1
        return self.op(vl,vr)
    
    def all_prod(self):
        return self.node[1]
    
    def get(self,k):
        return self.node[self.size+k]
    
    def max_right(self,l,f):
      if l==self.n:return self.n
      l+=self.size
      sm=self.e
      while True:
        while l&0:l>>=1
        if not f(self.op(sm,self.node[l])):
          while l<self.size:
            l<<=1
            if f(self.op(sm,self.node[l])):
              sm=self.op(sm,self.node[l])
              l+=1
          return l-self.size
        sm=self.op(sm,self.node[l])
        l+=1
        if l&-l==l:break
      return self.n
    
    def min_left(self,r,f):
      if r==0:return 0
      r+=self.size
      sm=self.e
      while True:
        r-=1
        while r>1 and r&1:r>>=1
        if not f(self.op(self.node[r],sm)):
          while r<self.size:
            r=2*r+1
            if f(self.op(self.node[r],sm)):
              sm=self.op(self.node[r],sm)
              r-=1
          return r+1-self.size
        sm=self.op(self.node[r],sm)
        if r&-r==r:break
      return 0

n=int(input())
A=list(map(int,input().split()))
q=int(input())
LR=[list(map(int,input().split())) for _ in range(q)]

f,g=[1]*n,[1]*n
for i in range(n-1):
    f[i]=int(A[i]<=A[i+1])
    g[i]=int(A[i]>=A[i+1])

f=SegTree(min,float('INF'),f)
g=SegTree(min,float('INF'),g)
for l,r in LR:
    if r-l==0:
        print(1,1)
    else:
        print(f.prod(l,r),g.prod(l,r))
0