Submission #147152

#	Time	Username	Problem	Language	Result	Execution time	Memory
147152		jh05013	Global Warming (CEOI18_glo)	Pypy 2	17 / 100	1863 ms	48788 KiB

glo

input = raw_input
range = xrange

class Fenwick:
    def __init__(_, size):
        _.arr = [0]*size
    
    def add(_, i, val):
        while i < len(_.arr): _.arr[i] = max(_.arr[i], val); i |= i+1
    
    def getsum(_, i):
        res = 0
        while i >= 0: res = max(res, _.arr[i]); i = (i&(i+1))-1
        return res

from bisect import bisect_left as bl
def xlis(L):
    # dp0[i] = "up to i, no change" = max {L[j]<L[i]} dp0[j]+1
    # dp1[i] = "up to i, change"    = max { {L[j]<L[i]} dp1[j]+1, {L[j]<L[i]+x} dp0[j]+1}
    S = sorted(L)
    F0 = Fenwick(n)
    F1 = Fenwick(n)
    j = bl(S, L[0])
    F0.add(j, 1)
    F1.add(j, 1)
    for i in range(1, n):
        j0 = bl(S, L[i])-1
        j1 = bl(S, L[i]+x)-1
        v0 = F0.getsum(j0) + 1
        v1 = max(F1.getsum(j0), F0.getsum(j1)) + 1
        F0.add(j0+1, v0)
        F1.add(j0+1, v1)
    return F1.getsum(n-1)
    
n, x = map(int,input().split())
seq = list(map(int,input().split()))
A = xlis(seq)
B = xlis([-x for x in reversed(seq)])
print(max(A, B))

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