Submission #518661

#	Time	Username	Problem	Language	Result	Execution time	Memory
518661		Nihal_9936	Global Warming (CEOI18_glo)	Pypy 3	100 / 100	222 ms	49380 KiB

glo

import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
from operator import itemgetter

sys.setrecursionlimit(5 * 10 ** 4)
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

pi = 3.1415926535
mod = 10 ** 9 + 7


def solve(ar,bol=0):
    ck = []
    ans = []

    for i in ar:
        if bol:
            x = i + d
            if not ck or ck[-1] < x:
                ans.append(len(ck) + 1)
            else:
                id = bisect_left(ck, x)
                ans.append(id + 1)
        if not ck or ck[-1]<i:
            ck.append(i)
            if not bol:
                ans.append(len(ck))
        else:
            id = bisect_left(ck,i)
            ck[id] = i
            if not bol:
                ans.append(id+1)
    return ans

n,d = map(int, input().split())
a = list(map(int,input().split()))
lr = solve(a)
rl = solve([-i for i in a][::-1], 1)[::-1]
ans = 0
for x,y in zip(lr,rl):
    ans = max(ans, x+y-1)
print(ans)

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25