Submission #1309336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309336		yyrtc	Global Warming (CEOI18_glo)	Pypy 3	0 / 100	680 ms	116460 KiB

glo

import sys
import threading
def solve():
    input = sys.stdin.readline

    n, x = map(int, input().split())
    t = list(map(int, input().split()))

    # ---------- Coordinate compression ----------
    vals = sorted(set(t))
    comp = {v: i+1 for i, v in enumerate(vals)}
    m = len(vals)

    a = [comp[v] for v in t]

    # ---------- Fenwick Tree (max) ----------
    class Fenwick:
        def __init__(self, n):
            self.n = n
            self.bit = [0] * (n + 1)

        def update(self, i, v):
            while i <= self.n:
                self.bit[i] = max(self.bit[i], v)
                i += i & -i

        def query(self, i):
            res = 0
            while i > 0:
                res = max(res, self.bit[i])
                i -= i & -i
            return res

    # ---------- LIS from left ----------
    L = [0] * n
    fw = Fenwick(m)
    for i in range(n):
        L[i] = fw.query(a[i] - 1) + 1
        fw.update(a[i], L[i])

    # ---------- LIS from right ----------
    R = [0] * n
    fw = Fenwick(m)
    for i in range(n-1, -1, -1):
        R[i] = fw.query(m - a[i]) + 1
        fw.update(m - a[i] + 1, R[i])

    # ---------- Answer without modification ----------
    ans = max(L)

    # ---------- Main trick: allow one shifted segment ----------
    # Prepare pairs (value, R[i])
    pairs = list(zip(t, R))
    pairs.sort()

    fw = Fenwick(m)

    j = 0
    for i in range(n):
        # Add all suffix elements with value <= t[i] + 2x
        while j < n and pairs[j][0] <= t[i] + 2 * x:
            fw.update(comp[pairs[j][0]], pairs[j][1])
            j += 1

        best_suffix = fw.query(m)
        ans = max(ans, L[i] + best_suffix)

    print(ans)

if __name__ == "__main__":
    solve()

Compilation message (stdout)

Compiling 'glo.py'...

=======
  adding: __main__.pyc (deflated 46%)

=======

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