oj.uz

Submission #147152

# Submission time Handle Problem Language Result Execution time Memory
147152 2019-08-28T06:08:26 Z jh05013 Global Warming (CEOI18_glo) PyPy
17 / 100
 1863 ms 48788 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11360 KB Output is correct
2 Correct 33 ms 11232 KB Output is correct
3 Correct 33 ms 11236 KB Output is correct
4 Correct 32 ms 11228 KB Output is correct
5 Correct 33 ms 11224 KB Output is correct
6 Correct 33 ms 11204 KB Output is correct
7 Correct 33 ms 11232 KB Output is correct
8 Incorrect 33 ms 11216 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11360 KB Output is correct
2 Correct 33 ms 11232 KB Output is correct
3 Correct 33 ms 11236 KB Output is correct
4 Correct 32 ms 11228 KB Output is correct
5 Correct 33 ms 11224 KB Output is correct
6 Correct 33 ms 11204 KB Output is correct
7 Correct 33 ms 11232 KB Output is correct
8 Incorrect 33 ms 11216 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11360 KB Output is correct
2 Correct 33 ms 11232 KB Output is correct
3 Correct 33 ms 11236 KB Output is correct
4 Correct 32 ms 11228 KB Output is correct
5 Correct 33 ms 11224 KB Output is correct
6 Correct 33 ms 11204 KB Output is correct
7 Correct 33 ms 11232 KB Output is correct
8 Incorrect 33 ms 11216 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1856 ms 48788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 659 ms 22028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 32788 KB Output is correct
2 Correct 1046 ms 34592 KB Output is correct
3 Correct 1863 ms 48772 KB Output is correct
4 Correct 1177 ms 42504 KB Output is correct
5 Correct 696 ms 28832 KB Output is correct
6 Correct 893 ms 41444 KB Output is correct
7 Correct 875 ms 44204 KB Output is correct
8 Correct 839 ms 31900 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11360 KB Output is correct
2 Correct 33 ms 11232 KB Output is correct
3 Correct 33 ms 11236 KB Output is correct
4 Correct 32 ms 11228 KB Output is correct
5 Correct 33 ms 11224 KB Output is correct
6 Correct 33 ms 11204 KB Output is correct
7 Correct 33 ms 11232 KB Output is correct
8 Incorrect 33 ms 11216 KB Output isn't correct
9 Halted 0 ms 0 KB -