Problem:


Range Update Query (RUQ)

Write a program which manipulates a sequence A = {a0, a1, . . .  , an&minus;1} with the following operations:

  
update(s, t, x): change as, as+1, ..., at to x.

  
find(i): output the value of ai.

Note that the initial values of ai (i = 0, 1, . . .  , n&minus;1) are  231-1.

Input

n q
query1
query2
:
queryq

  In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:

0 s t x 

  or

1 i

  The first digit represents the type of the query. '0' denotes update(s, t, x) and '1' denotes find(i).

Output

For each find operation, print the value.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

  0 ≤ s ≤ t < n

  0 ≤ i < n

  0 ≤ x < 231&minus;1
  

Sample Input 1

3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1

Sample Output 1

1
3

Sample Input 2

1 3
1 0
0 0 0 5
1 0

Sample Output 2

2147483647
5



Sample input:
3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1


Sample output:
1
3

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# DSL_2_D: Range Update Query


class SegmentTree:
    def __init__(self, n):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [-1] * self.size
        self.data[0] = 2**31 - 1

    def set_range(self, lo, hi, v):
        def _set_range(r, i, j, vv):
            if j < lo or i > hi:
                if vv != -1:
                    self.data[r] = vv
            elif lo <= i and j <= hi:
                self.data[r] = v
            else:
                if self.data[r] != -1:
                    vv = self.data[r]
                    self.data[r] = -1
                mid = i + (j - i)//2
                _set_range(r*2 + 1, i, mid, vv)
                _set_range(r*2 + 2, mid+1, j, vv)

        _set_range(0, 0, self.size//2, -1)

    def get(self, i):
        def _get(r, lo, hi):
            if self.data[r] != -1:
                return self.data[r]
            mid = lo + (hi - lo)//2
            if i <= mid:
                return _get(r*2 + 1, lo, mid)
            else:
                return _get(r*2 + 2, mid+1, hi)

        return _get(0, 0, self.size//2)


def run():
    n, q = [int(x) for x in input().split()]
    t = SegmentTree(n)

    for _ in range(q):
        com, *args = [x for x in input().split()]
        if com == '0':
            i, j, v = [int(x) for x in args]
            t.set_range(i, j, v)
        elif com == '1':
            i = int(args[0])
            print(t.get(i))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)
def update(Set,x,y,z):
    for i in range(x,y+1):
        Set[i] = z

def lazy_update(Set,i,x):
    Set[i] = x

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    sqrtN = 1
    while True:
        if(N >= _N):
            break
        sqrtN += 1
        N = sqrtN**2
    A = [2**31 - 1]*N
    lazy_A = [None]*sqrtN
    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            for i in range(0,sqrtN):
                if(i*sqrtN <= query[1] or query[2] <= (i+1)*sqrtN):
                    continue
                if(query[1] <= i*sqrtN and (i+1)*sqrtN <= query[2]):
                    if not (lazy_A[i] == query[3]):
                        lazy_update(lazy_A,i,query[3])
                else:
                    if(lazy_A[i] is not None):
                        A[i*sqrtN:(i+1)*sqrtN] = [lazy_A[i]]*sqrtN
                        lazy_A[i] = None
                    update(A,query[1],i*sqrtN-1,query[3])
                    update(A,(i+1)*sqrtN+1,query[2],query[3])
        # find
        if(query[0]==1):
            if(lazy_A[int(query[1]/sqrtN)] is not None):
                A[int(query[1]/sqrtN)*sqrtN:int(query[1]/sqrtN)*sqrtN+sqrtN] = [lazy_A[int(query[1]/sqrtN)]]*sqrtN
                lazy_A[int(query[1]/sqrtN)] = None
                #print("A update from lazy")
                #print(A)
            print(A[query[1]])
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)
def update(Set,x,y,z):
    for i in range(x,y+1):
        Set[i] = z

def lazy_update(Set,i,x):
    Set[i] = x

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    sqrtN = 1
    while True:
        if(N >= _N):
            break
        sqrtN += 1
        N = sqrtN**2
    A = [2**31 - 1]*N
    lazy_A = [None]*sqrtN
    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            for i in range(0,sqrtN):
                if((i+1)*sqrtN <= query[1] or query[2] <= i*sqrtN):
                    continue
                if(query[1] <= i*sqrtN and (i+1)*sqrtN <= query[2]):
                    if not (lazy_A[i] == query[3]):
                        lazy_update(lazy_A,i,query[3])
                else:
                    if(lazy_A[i] is not None):
                        A[i*sqrtN:(i+1)*sqrtN] = [lazy_A[i]]*sqrtN
                        lazy_A[i] = None
                    n = max(query[1],i*sqrtN)
                    m = min(query[2],(i+1)*sqrtN)
                    #print("max from {0} {1}".format(query[1],i*sqrtN))
                    #print("min from {0} {1}".format(query[2],(i+1)*sqrtN))
                    #print(n,m)
                    update(A,n,m,query[3])
                    #update(A,(i+1)*sqrtN+1,query[2],query[3])
            #print(A)
        # find
        if(query[0]==1):
            if(lazy_A[int(query[1]/sqrtN)] is not None):
                A[int(query[1]/sqrtN)*sqrtN:int(query[1]/sqrtN)*sqrtN+sqrtN] = [lazy_A[int(query[1]/sqrtN)]]*sqrtN
                lazy_A[int(query[1]/sqrtN)] = None
                #print("A update from lazy")
                #print(A)
            print(A[query[1]])
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)
INT_MAX = 2**31 - 1
lazy_init = (None,-1)

def update(tree,x,y,z,N):
    left = x + N #- 1
    right = y + N #- 1
    while True:
        if(left >= right):
            break
        if(right > 0):
            tree[right - 1] = z
        if(left > 0):
            tree[left - 1] = z

        left = math.floor((left + 1)/2)
        right = math.floor((right - 1)/2)

def find(tree,x,N):
    x += N - 1
    s = (INT_MAX, -1)
    while True:
        if(x <= 0):
            break
        if(tree[x][1] > s[1]):
            s = tree[x]
        x = math.floor((x - 1)/2)
    return s[0]
if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    while True:
        if(N >= _N):
            break
        N <<= 1
    if not (N == 1):
        A = [(INT_MAX,-1)]*(2*N - 1)
        lazy_A = [lazy_init]*(2*N - 1)
    else:
        A = [(INT_MAX,-1)]*(2*N)
        lazy_A = [lazy_init]*(2*N)

    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            update(A,query[1],query[2],(query[3],i),N)
            #print(A,lazy_A)
        # find
        if(query[0]==1):
            #z = find(A,lazy_A,query[1],query[1]+1,0,0,N,N)
            z = find(A,query[1],N)
            print(z)
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)
INT_MAX = 2**31 - 1

def update(tree,x,y,z,N):
    left = x + N #- 1
    right = y + N #- 1
    while True:
        if(left > right):
            break
        if(right > 0):
            tree[right - 1] = z
        if(left > 0):
            tree[left - 1] = z

        left = math.floor((left + 1)/2)
        right = math.floor((right - 1)/2)

def find(tree,x,N):
    x += N - 1
    s = (INT_MAX, -1)
    while True:
        if(x <= 0):
            break
        if(tree[x][1] > s[1]):
            s = tree[x]
        x = math.floor((x - 1)/2)
    return s[0]
if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    while True:
        if(N >= _N):
            break
        N <<= 1
    if not (N == 1):
        A = [(INT_MAX,-1)]*(2*N - 1)
    else:
        A = [(INT_MAX,-1)]*(2*N)

    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            update(A,query[1],query[2],(query[3],i),N)
            #print(A)
        # find
        if(query[0]==1):
            #z = find(A,lazy_A,query[1],query[1]+1,0,0,N,N)
            z = find(A,query[1],N)
            print(z)
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

Solution code:
import math

INT_MAX = 2147483647
MAX = 100003
n,q=(int(x) for x in input().split())
b= math.sqrt(n)

def update(x):
 
    for i in range(int(x*b),int(min(n-1,(x+1)*b))):a[i]=l[int(x)]
    l[int(x)]=-1;
    return;
 

if __name__=='__main__':
    a = [INT_MAX for i in range(n)]
    l = [-1 for i in range(n)]
    
   
    for i in range(q):
        t, *com = (int(x) for x in input().split())
        if t : 
            x = com[0]
            if l[int(x/b)] != -1:update(x/b)
            print(a[x])
        else:
            x,y,z = com
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,int(min(y,(x/b+1)*b))):a[i]=z
            for i in range(int(x/b)+1,int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(int(max(x,y/b**2)),y+1):a[i]=z

Submission status: Wrong Answer

Solution code:
import math

INT_MAX = 2147483647
MAX = 100003
n,q=(int(x) for x in input().split())
b= math.sqrt(n)


def judge_max(x,y):
    
    if x > y :return x
    else:return y 

def judge_min(x,y):
    if x > y :return y
    else :return x



def update(x):
 
    for i in range(int(x*b),int(judge_min(n-1,(x+1)*b))):a[i]=l[int(x)]
    l[int(x)]=-1;
    return;
 

if __name__=='__main__':
    a = [INT_MAX for i in range(n)]
    l = [-1 for i in range(n)]
    
   
    for i in range(q):
        t, *com = (int(x) for x in input().split())
        if t : 
            x = com[0]
            if l[int(x/b)] != -1:update(x/b)
            print(a[x])
        else:
            x,y,z = com
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,int(judge_min(y,(x/b+1)*b))):a[i]=z
            for i in range(int(x/b)+1,int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(int(judge_max(x,y/b**2)),y+1):a[i]=z

Submission status: Wrong Answer

Solution code:
import math

INT_MAX = 2147483647
MAX = 100003
n,q=(int(x) for x in input().split())
b= math.sqrt(n)


def judge_max(x,y):
    
    if x > y :return x
    else:return y 

def judge_min(x,y):
    if x > y :return y
    else :return x



def update(x_f):
    
    x = int(x_f)
    for i in range(int(x*b),int(judge_min(n-1,(x+1)*b))):a[i]=l[int(x)]
    l[int(x)]=-1;
    return;
 

if __name__=='__main__':
    a = [INT_MAX for i in range(n)]
    l = [-1 for i in range(n)]
    
   
    for i in range(q):
        t, *com = (int(x) for x in input().split())
        if t : 
            x = com[0]
            if l[int(x/b)] != -1:update(x/b)
            print(a[x])
        else:
            x,y,z = com
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,int(judge_min(y,(x/b+1)*b))):a[i]=z
            for i in range(int(x/b)+1,int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(int(judge_max(x,y/b**2)),y+1):a[i]=z

Submission status: Wrong Answer

Solution code:
import math

INT_MAX = 2147483647
MAX = 100003
n,q=(int(x) for x in input().split())
b= math.sqrt(n)
a = [INT_MAX for i in range(n)]
l = [-1 for i in range(n)]


def judge_max(x,y):
    
    if x > y :return x
    else:return y 

def judge_min(x,y):
    if x > y :return y
    else :return x



def update(x_f):
    
    x = int(x_f)
    for i in range(int(x*b),min(n-1,int((x+1)*b-1))+1):a[i]=l[x]
    l[x]=-1
    return
 

if __name__=='__main__':
        
   
    for j in range(q):
        t, *com = (int(x) for x in input().split())
        if t : 
            x = com[0]
            if l[int(x/b)] != -1:update(x/b)
            print(a[x])
        else:
            x,y,z = com
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,min(y,int((x/b+1)*b-1))+1):a[i]=z
            for i in range(int(x/b+1),int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(max(x,int(y/b**2)),y+1):a[i]=z

Submission status: Wrong Answer

Solution code:
#! -*- coding:utf-8 -*-
n,q = map(int,input().split())
query = [0] * q
for i in range(q):
    query[i] = input()
arr = [2**31 - 1] * n

for i in range(q):
    if len(query[i]) == 7:
        tmp = list(query[i].split())
        s = int(tmp[1])
        t = int(tmp[2])
        for i in range(s,t+1):
            arr[i] = tmp[3]
    else:
        tmp = list(query[i].split())
        print(arr[int(tmp[1])])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000)
def update(Set,x,y,z):
    for i in range(x,y+1):
        Set[i] = z

def lazy_update(Set,x,y,z):
    left = int(x/4)
    if((x%4)!=0):
        left = left + 1
    right = int(y/4)
    for i in range(left,right):
        Set[i] = z
    return left*4,right*4

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    A = [2**31 - 1]*_N
    N = 1
    while True:
        if(N*4 >= _N):
            break
        N += 1
    lazy_A = [None]*N
    #print(A,lazy_A)
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            if(lazy_A[int(query[1]/4)] is not None or lazy_A[int(query[2]/4)] is not None):
                for i in range(int(query[1]/4),int(query[2]/4)+1):
                    if(lazy_A[i] is None):
                        continue
                    A[i*4:i*4+4] = [lazy_A[i]]*4
                    lazy_A[i] = None
                #print("A update from lazy")
                #print(A)
                #print(lazy_A)
                update(A,query[1],query[2],query[3])
                #print("update A")
                #print(A)
            if(lazy_A[int(query[1]/4)] is None or lazy_A[int(query[2]/4)] is None):
                if(query[2] - query[1] < 4):
                    update(A,query[1],query[2],query[3])
                    #print("A update")
                    #print(A)
                else:
                    right, left = lazy_update(lazy_A,query[1],query[2],query[3])
                    #print("lazy update")
                    #print(lazy_A)
                    if(right > 0):
                        #print("A left update")
                        update(A,query[1],right-1,query[3])
                        #print(A)
                    if(left > 0):
                        #print("A right update")
                        update(A,left,query[2],query[3])
                        #print(A)
        # find
        if(query[0]==1):
            if(lazy_A[int(query[1]/4)] is not None):
                A[int(query[1]/4)*4:int(query[1]/4)*4+4] = [lazy_A[int(query[1]/4)]]*4
                lazy_A[int(query[1]/4)] = None
                #print("A update from lazy")
                #print(A)
            print(A[query[1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
sys.setrecursionlimit(20000)
def update(Set,x,y,z):
    for i in range(x,y+1):
        Set[i] = z

def lazy_update(Set,x,y,z):
    left = int(x/4)
    if((x%4)!=0):
        left = left + 1
    right = int(y/4)
    for i in range(left,right):
        Set[i] = z
    return left*4,right*4

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    A = [2**31 - 1]*_N
    N = 1
    while True:
        if(N*4 >= _N):
            break
        N += 1
    lazy_A = [None]*N
    #start = time.time()
    #print(A,lazy_A)
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            if(lazy_A[int(query[1]/4)] is not None or lazy_A[int(query[2]/4)] is not None):
                for i in range(int(query[1]/4),int(query[2]/4)+1):
                    if(lazy_A[i] is None):
                        continue
                    A[i*4:i*4+4] = [lazy_A[i]]*4
                    lazy_A[i] = None
                #print("A update from lazy")
                #print(A)
                #print(lazy_A)
                update(A,query[1],query[2],query[3])
                #print("update A")
                #print(A)
            elif(lazy_A[int(query[1]/4)] is None or lazy_A[int(query[2]/4)] is None):
                if(query[2] - query[1] < 4):
                    update(A,query[1],query[2],query[3])
                    #print("A update")
                    #print(A)
                else:
                    right, left = lazy_update(lazy_A,query[1],query[2],query[3])
                    #print("lazy update")
                    #print(lazy_A)
                    if(right > 0):
                        #print("A left update")
                        update(A,query[1],right-1,query[3])
                        #print(A)
                    if(left > 0):
                        #print("A right update")
                        update(A,left,query[2],query[3])
                        #print(A)
        # find
        if(query[0]==1):
            if(lazy_A[int(query[1]/4)] is not None):
                A[int(query[1]/4)*4:int(query[1]/4)*4+4] = [lazy_A[int(query[1]/4)]]*4
                lazy_A[int(query[1]/4)] = None
                #print("A update from lazy")
                #print(A)
            print(A[query[1]])
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)
def update(Set,x,y,z):
    for i in range(x,y+1):
        Set[i] = z

def lazy_update(Set,i,x):
    Set[i] = x

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    sqrtN = 1
    while True:
        if(N >= _N):
            break
        sqrtN += 1
        N = sqrtN**2
    A = [2**31 - 1]*N
    lazy_A = [None]*sqrtN
    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            for i in range(0,sqrtN):
                if((i+1)*sqrtN <= query[1] or query[2] <= i*sqrtN):
                    pass
                if(query[1] <= i*sqrtN and (i+1)*sqrtN <= query[2]):
                    if not (lazy_A[i] == query[3]):
                        lazy_update(lazy_A,i,query[3])
                else:
                    if(lazy_A[i] is not None):
                        A[i*sqrtN:(i+1)*sqrtN] = [lazy_A[i]]*sqrtN
                        lazy_A[i] = None
                    n = max(query[1],i*sqrtN)
                    m = min(query[2],(i+1)*sqrtN)
                    #print("max from {0} {1}".format(query[1],i*sqrtN))
                    #print("min from {0} {1}".format(query[2],(i+1)*sqrtN))
                    #print(n,m)
                    update(A,n,m,query[3])
                    #update(A,(i+1)*sqrtN+1,query[2],query[3])
            #print(A)
        # find
        if(query[0]==1):
            if(lazy_A[int(query[1]/sqrtN)] is not None):
                A[int(query[1]/sqrtN)*sqrtN:int(query[1]/sqrtN)*sqrtN+sqrtN] = [lazy_A[int(query[1]/sqrtN)]]*sqrtN
                lazy_A[int(query[1]/sqrtN)] = None
                #print("A update from lazy")
                #print(A)
            print(A[query[1]])
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)

def lazy_tree_merge(lazy,tree,i,N):
    if(lazy[i][0] is not None):
        tree[i] = lazy[i]
        if(i < N-1):
            lazy[i*2+1] = lazy[i]
            lazy[i*2+2] = lazy[i]
        lazy[i] = (None,-1)

def update(tree,lazy,x,y,k,l,r,i,z,N):
    if (r <= x or y <= l):
        lazy_tree_merge(lazy,tree,k,N)
        return True
    if ( x <= l and r <= y):
        lazy[k] = (z,i)
        lazy_tree_merge(lazy,tree,k,N)
        return True

    lazy_tree_merge(lazy,tree,k,N)
    update(tree, lazy, x, y, k*2 + 1, l, int((l+r)/2), i, z, N)
    #update(tree, lazy, x, y, k*2 + 2, l, int((l+r)/2), i, z, N)
    update(tree, lazy, x, y, k*2 + 2, int((l+r)/2), r, i, z, N)
    if(tree[k*2+1][1] < tree[k*2+2][1]):
        tree[k] = tree[k*2+2]
    else:
        tree[k] = tree[k*2+1]
    #tree[k] = min(tree[k*2+1], tree[k*2+2])

def find(tree,lazy,x,y,k,l,r,N):

    if (r <= x or y <= l):
        return 2**31 - 1
    if ( x <= l and r <= y):
        lazy_tree_merge(lazy,tree,k,N)
        return tree[k][0]

    lazy_tree_merge(lazy,tree,k,N)
    v_left = find(tree, lazy_A, x, y, k*2 + 1, l, int((l+r)/2), N)
    v_right = find(tree, lazy_A, x, y, k*2 + 2, int((l+r)/2), r, N)
    #print(v_left)
    #print(v_right)
    return min(v_left, v_right)

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    INT_MAX = 2**31 - 1
    N = 1
    while True:
        if(N >= _N):
            break
        N *= 2
    if not (N == 1):
        A = [(INT_MAX,-1)]*(2*N - 1)
        lazy_A = [(None,-1)]*(2*N - 1)
    else:
        A = [(INT_MAX,-1)]*(2*N)
        lazy_A = [(None,-1)]*(2*N)

    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            update(A,lazy_A,query[1],query[2]+1,0,0,N,i,query[3],N)
            #print(A,lazy_A)
        # find
        if(query[0]==1):
            z = find(A,lazy_A,query[1],query[1]+1,0,0,N,N)
            print(z)
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(20000)
INT_MAX = 2**31 - 1
lazy_init = (None,-1)
def lazy_tree_merge(lazy,tree,i,N):
    if(lazy[i][0] is not None):
        tree[i] = lazy[i]
        if(i < N-1):
            lazy[i*2+1] = lazy[i]
            lazy[i*2+2] = lazy[i]
        lazy[i] = lazy_init

def update(tree,lazy,x,y,k,l,r,i,z,N):
    if (r <= x or y <= l):
        lazy_tree_merge(lazy,tree,k,N)
        return True
    if ( x <= l and r <= y):
        lazy[k] = (z,i)
        lazy_tree_merge(lazy,tree,k,N)
        return True

    lazy_tree_merge(lazy,tree,k,N)
    center = int((l+r)/2)
    update(tree, lazy, x, y, k*2 + 1, l, center, i, z, N)
    #update(tree, lazy, x, y, k*2 + 2, l, int((l+r)/2), i, z, N)
    update(tree, lazy, x, y, k*2 + 2, center, r, i, z, N)
    if(tree[k*2+1][1] < tree[k*2+2][1]):
        tree[k] = tree[k*2+2]
    else:
        tree[k] = tree[k*2+1]

def find(tree,lazy,x,y,k,l,r,N):

    if (r <= x or y <= l):
        return INT_MAX
    if ( x <= l and r <= y):
        lazy_tree_merge(lazy,tree,k,N)
        return tree[k][0]

    lazy_tree_merge(lazy,tree,k,N)
    v_left = find(tree, lazy_A, x, y, k*2 + 1, l, int((l+r)/2), N)
    v_right = find(tree, lazy_A, x, y, k*2 + 2, int((l+r)/2), r, N)
    return min(v_left, v_right)

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    while True:
        if(N >= _N):
            break
        N <<= 1
    if not (N == 1):
        A = [(INT_MAX,-1)]*(2*N - 1)
        lazy_A = [lazy_init]*(2*N - 1)
    else:
        A = [(INT_MAX,-1)]*(2*N)
        lazy_A = [lazy_init]*(2*N)

    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            update(A,lazy_A,query[1],query[2]+1,0,0,N,i,query[3],N)
            #print(A,lazy_A)
        # find
        if(query[0]==1):
            z = find(A,lazy_A,query[1],query[1]+1,0,0,N,N)
            print(z)

Submission status: Time Limit Exceeded

Solution code:
import math

INT_MAX = 2147483647
MAX = 100003
n,q=(int(x) for x in input().split())
b= int(math.sqrt(n))



def update(x_f):
    
    x = int(x_f)
    for i in range(int(x*b),min(n-1,int((x+1)*b-1))+1):a[i]=l[x]
    l[x]=-1
    return
 

if __name__=='__main__':
        
    a = [INT_MAX for i in range(n)]
    l = [-1 for i in range(n)]
    
    for j in range(q):
        t, *com = (int(x) for x in input().split())
        if t : 
            x = com[0]
            if l[int(x/b)] != -1:update(x/b)
            print(a[x])
        else:
            x,y,z = com
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,min(y,int((x/b+1)*b-1))+1):a[i]=z
            for i in range(int(x/b+1),int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(max(x,int(y/b**2)),y+1):a[i]=z

Submission status: Time Limit Exceeded

Solution code:
import math

INT_MAX = 2147483647
MAX = 100003
n,q= l = map(int, raw_input().split())
b= int(math.sqrt(n))



def update(x_f):
    
    x = int(x_f)
    for i in range(int(x*b),min(n-1,int((x+1)*b-1))+1):a[i]=l[x]
    l[x]=-1
    return
 

if __name__=='__main__':
        
    a = [INT_MAX for i in range(n)]
    l = [-1 for i in range(n)]
    
    for j in range(q):
        t = map(int, raw_input().split())
        if t[0] : 
            x = t[1]
            if l[int(x/b)] != -1:update(x/b)
            print a[x]
        else:
            t0,x,y,z=t
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,min(y,int((x/b+1)*b-1))+1):a[i]=z
            for i in range(int(x/b+1),int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(max(x,int(y/b**2)),y+1):a[i]=z

Submission status: Time Limit Exceeded

Solution code:
import math

INT_MAX = 2147483647
n,q=(int(x) for x in input().split())
b= int(math.sqrt(n))

def update(x_f):
    
    x = int(x_f)
    for i in range(int(x*b),min(n-1,int((x+1)*b-1))+1):a[i]=l[x]
    l[x]=-1
    return
 

if __name__=='__main__':
        
    a = [INT_MAX for i in range(n)]
    l = [-1 for i in range(n)]
    
    for j in range(q):
        t, *com = (int(x) for x in input().split())
        if t : 
            x = com[0]
            if l[int(x/b)] != -1:update(x/b)
            print(a[x])
        else:
            x,y,z = com
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,min(y,int((x/b+1)*b-1))+1):a[i]=z
            for i in range(int(x/b+1),int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(max(x,int(y/b**2)),y+1):a[i]=z

Submission status: Time Limit Exceeded

Solution code:
import math

INT_MAX = 2147483647
n,q= l = map(int, raw_input().split())
b= int(math.sqrt(n))



def update(x_f):
    
    x = int(x_f)
    for i in range(int(x*b),min(n-1,int((x+1)*b-1))+1):a[i]=l[x]
    l[x]=-1
    return
 

if __name__=='__main__':
        
    a = [INT_MAX for i in range(n)]
    l = [-1 for i in range(n)]
    
    for j in range(q):
        t = map(int, raw_input().split())
        if t[0] : 
            x = t[1]
            if l[int(x/b)] != -1:update(x/b)
            print a[x]
        else:
            t0,x,y,z=t
            if l[int(x/b)] != -1:update(x/b)
            for i in range(x,min(y,int((x/b+1)*b-1))+1):a[i]=z
            for i in range(int(x/b+1),int(y/b)):l[i]=z
            if l[int(y/b)] != -1:update(y/b)
            for i in range(max(x,int(y/b**2)),y+1):a[i]=z

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
a = [2 ** 31 - 1] * n
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        s, t, x = map(int, query[1:])
        a[s:t + 1] = [x] * (t - s + 1)
    else:
        print(a[int(query[1])])

Submission status: Time Limit Exceeded

Solution code:
#! -*- coding:utf-8 -*-
n,q = map(int,input().split())
query = [0] * q
for i in range(q):
    query[i] = input()
arr = [2**31 - 1] * n

for i in range(q):
    tmp = list(query[i].split())    
    if len(tmp) == 4:

        s = int(tmp[1])
        t = int(tmp[2])
        for i in range(s,t+1):
            arr[i] = tmp[3]
    else:
        print(arr[int(tmp[1])])

Submission status: Time Limit Exceeded

Solution code:
import sys
_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
MAX = pow(2, 31) - 1

A = [MAX] * n
for q in qlist:
    cmd = int(q[0])
    if cmd == 0:
        s = int(q[1])
        t = int(q[2])+1
        add = [int(q[3])] * (t - s)
        A = A[:s] + add + A[t:]
    elif cmd == 1:
        print(A[int(q[1])])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

a = []

def update(s,t,x):
	for i in range(s,t+1):
		a[i] = x

def find(i):
	print(a[i])

n,q = map(int,input().split())

for i in range(n):
	a.append(2 ** 31 - 1)

for i in range(q):
	num = list(map(int,input().split()))
	if num[0] == 0:
		update(num[1],num[2],num[3])
	if num[0] == 1:
		find(num[1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_2_D: Range Update Query


class SegmentTree:
    INITIAL_VALUE = 2**31 - 1
    DIVIDED = -1

    def __init__(self, n):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [-1] * self.size
        self.data[0] = self.INITIAL_VALUE

    def set_range(self, lo, hi, v):
        def _set_range(r, i, j, vv):
            if j < lo or i > hi:
                if vv != self.DIVIDED:
                    self.data[r] = vv
            elif lo <= i and j <= hi:
                self.data[r] = v
            else:
                if self.data[r] != self.DIVIDED:
                    if vv == self.DIVIDED:
                        vv = self.data[r]
                    self.data[r] = self.DIVIDED
                mid = i + (j - i)//2
                _set_range(r*2 + 1, i, mid, vv)
                _set_range(r*2 + 2, mid+1, j, vv)

        _set_range(0, 0, self.size//2, self.DIVIDED)

    def get(self, i):
        def _get(r, lo, hi):
            if self.data[r] != self.DIVIDED:
                return self.data[r]
            mid = lo + (hi - lo)//2
            if i <= mid:
                return _get(r*2 + 1, lo, mid)
            else:
                return _get(r*2 + 2, mid+1, hi)

        return _get(0, 0, self.size//2)


def run():
    n, q = [int(x) for x in input().split()]
    t = SegmentTree(n)

    for _ in range(q):
        com, *args = [x for x in input().split()]
        if com == '0':
            i, j, v = [int(x) for x in args]
            t.set_range(i, j, v)
        elif com == '1':
            i = int(args[0])
            print(t.get(i))


if __name__ == '__main__':
    run()