124112024-12-17 11:44:2442Síkság (55)pypy3Time limit exceeded 19/55303ms32000 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

def solv():
    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)

solv()
SubtaskSumTestVerdictTimeMemory
base19/55
1Accepted0/052ms21228 KiB
2Time limit exceeded0/0261ms25184 KiB
3Accepted2/245ms21172 KiB
4Accepted2/245ms21188 KiB
5Accepted2/243ms21232 KiB
6Accepted2/257ms21696 KiB
7Accepted3/356ms21612 KiB
8Accepted2/2143ms23532 KiB
9Accepted3/3140ms24136 KiB
10Time limit exceeded0/3270ms25580 KiB
11Time limit exceeded0/3256ms26604 KiB
12Accepted3/3112ms23344 KiB
13Runtime error0/368ms32000 KiB
14Runtime error0/376ms32000 KiB
15Runtime error0/383ms32000 KiB
16Runtime error0/367ms32000 KiB
17Runtime error0/368ms32000 KiB
18Runtime error0/368ms32000 KiB
19Runtime error0/382ms32000 KiB
20Runtime error0/368ms32000 KiB
21Time limit exceeded0/3303ms29200 KiB
22Runtime error0/371ms32000 KiB