124092024-12-17 11:41:4542Síkság (55)python3Időlimit túllépés 19/55300ms14368 KiB
# O(N*log^2)
from sys import stdin
input=stdin.readline

class minSegmentTree:
    def __init__(self):
        self.tree = None

    def buildTree(self,List):
        n = len(List)
        self.tree = [0 for i in range(2*n)]

        for i in range(n):
            self.tree[i+n] = List[i]

        for i in range(n-1,0,-1):
            self.tree[i] = min(self.tree[i<<1] , self.tree[i<<1 | 1])

    def minInRange(self, left, right):
        n = len(self.tree)//2
        result = self.tree[n+left]
        left += n
        right += n

        while left<right:
            if left&1:
                result = min(result,self.tree[left])
                left += 1
            if right&1:
                right -= 1
                result = min(result,self.tree[right])

            left >>= 1
            right >>= 1

        return result

class maxSegmentTree:
    def __init__(self):
        self.tree = None

    def buildTree(self,List):
        n = len(List)
        self.tree = [0 for i in range(2*n)]

        for i in range(n):
            self.tree[i+n] = List[i]

        for i in range(n-1,0,-1):
            self.tree[i] = max(self.tree[i<<1] , self.tree[i<<1 | 1])

    def maxInRange(self, left, right):
        n = len(self.tree)//2
        result = self.tree[n+left]
        left += n
        right += n

        while left<right:
            if left&1:
                result = max(result,self.tree[left])
                left += 1
            if right&1:
                right -= 1
                result = max(result,self.tree[right])

            left >>= 1
            right >>= 1

        return result
       
N=int(input())
A=list(map(int,input().split()))

minTree=minSegmentTree()
minTree.buildTree(A)
maxTree=maxSegmentTree()
maxTree.buildTree(A)

start=0
length=1

for i in range(1,len(A)):
    if maxTree.maxInRange(0,i+1)-minTree.minInRange(0,i+1) <= 1:
        if i+1>length:
            start=0
            length=i+1
    else:
        lo=0
        hi=i
        while hi-lo>1:
            mid=(hi+lo)//2
            if maxTree.maxInRange(mid,i+1)-minTree.minInRange(mid,i+1)<=1:
                hi=mid
            else:
                lo=mid
        if i+1-hi>length:
            start=hi
            length=i+1-hi
                  
print(length,start+1)
RészfeladatÖsszpontTesztVerdiktIdőMemória
base19/55
1Elfogadva0/017ms3384 KiB
2Időlimit túllépés0/0284ms4856 KiB
3Elfogadva2/217ms3384 KiB
4Elfogadva2/217ms3388 KiB
5Elfogadva2/217ms3388 KiB
6Elfogadva2/218ms3372 KiB
7Elfogadva3/318ms3384 KiB
8Elfogadva2/279ms3492 KiB
9Elfogadva3/368ms3400 KiB
10Időlimit túllépés0/3280ms4664 KiB
11Időlimit túllépés0/3277ms4064 KiB
12Elfogadva3/3125ms4404 KiB
13Időlimit túllépés0/3275ms14252 KiB
14Időlimit túllépés0/3300ms7968 KiB
15Időlimit túllépés0/3280ms12504 KiB
16Időlimit túllépés0/3284ms14368 KiB
17Időlimit túllépés0/3277ms14264 KiB
18Időlimit túllépés0/3300ms14344 KiB
19Időlimit túllépés0/3289ms14144 KiB
20Időlimit túllépés0/3282ms14156 KiB
21Időlimit túllépés0/3287ms9484 KiB
22Időlimit túllépés0/3296ms12144 KiB