Submission #518661

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
518661	2022-01-24T11:41:22 Z	Nihal_9936	Global Warming (CEOI18_glo)	PyPy 3	100 / 100	222 ms	49380 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	18520 KB	Output is correct
2	Correct	39 ms	18480 KB	Output is correct
3	Correct	43 ms	18436 KB	Output is correct
4	Correct	53 ms	18400 KB	Output is correct
5	Correct	44 ms	18344 KB	Output is correct
6	Correct	38 ms	18380 KB	Output is correct
7	Correct	39 ms	18432 KB	Output is correct
8	Correct	40 ms	18412 KB	Output is correct
9	Correct	56 ms	18468 KB	Output is correct
10	Correct	40 ms	18380 KB	Output is correct
11	Correct	39 ms	18348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	18520 KB	Output is correct
2	Correct	39 ms	18480 KB	Output is correct
3	Correct	43 ms	18436 KB	Output is correct
4	Correct	53 ms	18400 KB	Output is correct
5	Correct	44 ms	18344 KB	Output is correct
6	Correct	38 ms	18380 KB	Output is correct
7	Correct	39 ms	18432 KB	Output is correct
8	Correct	40 ms	18412 KB	Output is correct
9	Correct	56 ms	18468 KB	Output is correct
10	Correct	40 ms	18380 KB	Output is correct
11	Correct	39 ms	18348 KB	Output is correct
12	Correct	40 ms	18388 KB	Output is correct
13	Correct	44 ms	18444 KB	Output is correct
14	Correct	42 ms	18436 KB	Output is correct
15	Correct	42 ms	18440 KB	Output is correct
16	Correct	46 ms	18420 KB	Output is correct
17	Correct	39 ms	18396 KB	Output is correct
18	Correct	38 ms	18392 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	18520 KB	Output is correct
2	Correct	39 ms	18480 KB	Output is correct
3	Correct	43 ms	18436 KB	Output is correct
4	Correct	53 ms	18400 KB	Output is correct
5	Correct	44 ms	18344 KB	Output is correct
6	Correct	38 ms	18380 KB	Output is correct
7	Correct	39 ms	18432 KB	Output is correct
8	Correct	40 ms	18412 KB	Output is correct
9	Correct	56 ms	18468 KB	Output is correct
10	Correct	40 ms	18380 KB	Output is correct
11	Correct	39 ms	18348 KB	Output is correct
12	Correct	40 ms	18388 KB	Output is correct
13	Correct	44 ms	18444 KB	Output is correct
14	Correct	42 ms	18436 KB	Output is correct
15	Correct	42 ms	18440 KB	Output is correct
16	Correct	46 ms	18420 KB	Output is correct
17	Correct	39 ms	18396 KB	Output is correct
18	Correct	38 ms	18392 KB	Output is correct
19	Correct	80 ms	20688 KB	Output is correct
20	Correct	56 ms	19844 KB	Output is correct
21	Correct	58 ms	19908 KB	Output is correct
22	Correct	73 ms	20416 KB	Output is correct
23	Correct	59 ms	19788 KB	Output is correct
24	Correct	54 ms	19660 KB	Output is correct
25	Correct	54 ms	19692 KB	Output is correct
26	Correct	56 ms	19696 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	47720 KB	Output is correct
2	Correct	222 ms	47784 KB	Output is correct
3	Correct	215 ms	47696 KB	Output is correct
4	Correct	220 ms	47660 KB	Output is correct
5	Correct	168 ms	46596 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	28004 KB	Output is correct
2	Correct	126 ms	27532 KB	Output is correct
3	Correct	105 ms	27008 KB	Output is correct
4	Correct	93 ms	27400 KB	Output is correct
5	Correct	51 ms	18504 KB	Output is correct
6	Correct	85 ms	27496 KB	Output is correct
7	Correct	106 ms	27460 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	36272 KB	Output is correct
2	Correct	138 ms	35892 KB	Output is correct
3	Correct	196 ms	49380 KB	Output is correct
4	Correct	156 ms	46756 KB	Output is correct
5	Correct	125 ms	33760 KB	Output is correct
6	Correct	130 ms	46300 KB	Output is correct
7	Correct	137 ms	47160 KB	Output is correct
8	Correct	134 ms	36368 KB	Output is correct

Subtask #7
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	18520 KB	Output is correct
2	Correct	39 ms	18480 KB	Output is correct
3	Correct	43 ms	18436 KB	Output is correct
4	Correct	53 ms	18400 KB	Output is correct
5	Correct	44 ms	18344 KB	Output is correct
6	Correct	38 ms	18380 KB	Output is correct
7	Correct	39 ms	18432 KB	Output is correct
8	Correct	40 ms	18412 KB	Output is correct
9	Correct	56 ms	18468 KB	Output is correct
10	Correct	40 ms	18380 KB	Output is correct
11	Correct	39 ms	18348 KB	Output is correct
12	Correct	40 ms	18388 KB	Output is correct
13	Correct	44 ms	18444 KB	Output is correct
14	Correct	42 ms	18436 KB	Output is correct
15	Correct	42 ms	18440 KB	Output is correct
16	Correct	46 ms	18420 KB	Output is correct
17	Correct	39 ms	18396 KB	Output is correct
18	Correct	38 ms	18392 KB	Output is correct
19	Correct	80 ms	20688 KB	Output is correct
20	Correct	56 ms	19844 KB	Output is correct
21	Correct	58 ms	19908 KB	Output is correct
22	Correct	73 ms	20416 KB	Output is correct
23	Correct	59 ms	19788 KB	Output is correct
24	Correct	54 ms	19660 KB	Output is correct
25	Correct	54 ms	19692 KB	Output is correct
26	Correct	56 ms	19696 KB	Output is correct
27	Correct	219 ms	47720 KB	Output is correct
28	Correct	222 ms	47784 KB	Output is correct
29	Correct	215 ms	47696 KB	Output is correct
30	Correct	220 ms	47660 KB	Output is correct
31	Correct	168 ms	46596 KB	Output is correct
32	Correct	112 ms	28004 KB	Output is correct
33	Correct	126 ms	27532 KB	Output is correct
34	Correct	105 ms	27008 KB	Output is correct
35	Correct	93 ms	27400 KB	Output is correct
36	Correct	51 ms	18504 KB	Output is correct
37	Correct	85 ms	27496 KB	Output is correct
38	Correct	106 ms	27460 KB	Output is correct
39	Correct	149 ms	36272 KB	Output is correct
40	Correct	138 ms	35892 KB	Output is correct
41	Correct	196 ms	49380 KB	Output is correct
42	Correct	156 ms	46756 KB	Output is correct
43	Correct	125 ms	33760 KB	Output is correct
44	Correct	130 ms	46300 KB	Output is correct
45	Correct	137 ms	47160 KB	Output is correct
46	Correct	134 ms	36368 KB	Output is correct
47	Correct	144 ms	35888 KB	Output is correct
48	Correct	159 ms	36312 KB	Output is correct
49	Correct	217 ms	47892 KB	Output is correct
50	Correct	192 ms	46852 KB	Output is correct
51	Correct	134 ms	44824 KB	Output is correct
52	Correct	156 ms	46044 KB	Output is correct
53	Correct	136 ms	45744 KB	Output is correct
54	Correct	138 ms	47908 KB	Output is correct
55	Correct	221 ms	47948 KB	Output is correct

Submission #518661

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
25.0 / 25.0