1552F - Telepanting - CodeForces Solution


binary search data structures dp sortings *2200

Please click on ads to support us..

Python Code:



n = int(input())

X, Y, S = [], [], []
P = 998244353

T = [0]*(n+1)


def findIndex(L, p):
    
    
    n = len(L)
    
    l, r = 0, n
    guess = n // 2
    
    while r > l:
        guess = (r+l) // 2
        
        if L[guess] <= p:
            l = guess + 1
            
        elif L[guess] > p:
            r = guess
    
    return l


for i in range(n):
    xi, yi, si = map(int, input().split())
    
    X.append(xi)
    Y.append(yi)
    S.append(si)
    
    j = findIndex(X, yi)
        
    T[i+1] = (xi-yi + 2*T[i] - T[j]) % P

xn = X[-1]
total = xn+1
Test = [0]*n

for i in range(n):
    si = S[i]
    
        
    total += (T[i+1]-T[i]) * si
    total %= P
    

print(total)


Comments

Submit
0 Comments
More Questions

84. Largest Rectangle in Histogram
60. Permutation Sequence
42. Trapping Rain Water
32. Longest Valid Parentheses
Cutting a material
Bubble Sort
Number of triangles
AND path in a binary tree
Factorial equations
Removal of vertices
Happy segments
Cyclic shifts
Zoos
Build a graph
Almost correct bracket sequence
Count of integers
Differences of the permutations
Doctor's Secret
Back to School
I am Easy
Teddy and Tweety
Partitioning binary strings
Special sets
Smallest chosen word
Going to office
Color the boxes
Missing numbers
Maximum sum
13 Reasons Why
Friend's Relationship