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: Accepted

Solution code:
class RUQ(object):
    INF = 2 ** 31 - 1

    def __init__(self, num) -> None:
        n = 1
        while n <= num:
            n = n * 2
        self.n = n
        self.val = [self.INF] * (2 * n - 1)

    def update(self, beg: int, end: int, k: int, l: int, r: int, x: int) -> None:
        if (l == beg and r == end):
            self.val[k] = x
            return
        cv = self.val[k]
        if (cv != -1):
            self.val[k * 2] = self.val[k * 2 + 1] = cv
            self.val[k] = -1
        mid = (l + r) // 2
        if (end <= mid):
            self.update(beg, end, k * 2, l, mid, x)
        elif (beg > mid):
            self.update(beg, end, k * 2 + 1, mid + 1, r, x)
        else:
            self.update(beg, mid, k * 2, l, mid, x)
            self.update(mid + 1, end, k * 2 + 1, mid + 1, r, x)

    def find(self, k: int, l: int, r: int, idx: int) -> int:
        if self.val[k] != -1:
            return self.val[k]
        mid = (l + r) // 2
        if (idx <= mid):
            return self.find(k * 2, l, mid, idx)
        else:
            return self.find(k * 2 + 1, mid + 1, r, idx)


if __name__ == "__main__":
    n, q = map(lambda x: int(x), input().split())
    ruq = RUQ(n)

    for _ in range(q):
        com, *v = map(lambda x: int(x), input().split())
        if (0 == com):
            ruq.update(v[0], v[1], 1, 0, n - 1, v[2])
        else:
            print(f"{ruq.find(1, 0, n - 1, v[0])}")

Submission status: Accepted

Solution code:
class SegmentTree():
    """区間更新、一点取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: 区間[begin, end)をvalに変更する
    get_val: i番目の値を求める
    """
    def __init__(self, n):
        self.update_cnt = 0
        self.n = n
        self.size = 1
        INF = 2**31 - 1
        while self.size < n:
            self.size *= 2
        self.node = [[self.update_cnt, INF] for i in range(2*self.size - 1)]

    def update(self, begin, end, val):
        self.update_cnt += 1
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = [self.update_cnt, val]
            if (begin - 1) & 1:
                self.node[begin] = [self.update_cnt, val]
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = max(val, self.node[i])
        return val[1]


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(q)]

st = SegmentTree(n)
for i in range(q):
    if info[i][0] == 0:
        s, t, val = info[i][1], info[i][2], info[i][3]
        st.update(s, t + 1, val)
    else:
        s = info[i][1]
        print(st.get_val(info[i][1]))

Submission status: Accepted

Solution code:
# AOJ DSL_2_D
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D

INF = (-1, 2**31 - 1)
line = input()
n, q = list(map(int, line.split()))
N = 1
while N < n + 1:
    N *= 2
a = [INF for _ in range(0, 2 * N - 1)]

def find(i, k, l, r):
    z = a[0]
    while True:
        m = (l + r) // 2
        if i < m:
            k = k * 2 + 1
            r = m
        else:
            k = k * 2 + 2
            l = m
        z = max(z, a[k])
        if k >= N - 1:
            break
    return z[1]

def update(s, t, x, k, l, r):
    if r <= s or t <= l:
        return
    elif s <= l and r <= t:
        a[k] = x
        return
    m = (l + r) // 2
    update(s, t, x, k * 2 + 1, l, m)
    update(s, t, x, k * 2 + 2, m, r)
    return

for t in range(0, q):
    line = input()
    qu = list(map(int, line.split()))
    if qu[0] == 0:
        update(qu[1], qu[2]+1, (t, qu[3]), 0, 0, N)
    elif qu[0] == 1:
        ans = find(qu[1], 0, 0, N)
        print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())

size = 2**((n-1).bit_length())
tree = [None]*(size*2)
INF = (-1, 2**31-1)

def _find(i):
    ind = size+i
    s = INF
    while ind:
        if tree[ind]:
            s = max(s, tree[ind])
        ind = ind//2
    return s
def find(i):
    return _find(i)[1]

def update(s, t, v):
    L = s+size;R = t+size
    while L<R:
        if R&1:
            R-=1
            tree[R]=v
        if L&1:
            tree[L]=v
            L+=1
        L>>=1;R>>=1

ans = []
for i in range(q):
    a, *b = map(int, input().split())
    if a:ans.append(find(b[0]))
    else:update(b[0],b[1]+1,(i,b[2]))
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys


# 区間更新一点取得
class RangeUpdateQuery:
    def __init__(self, n, initial=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INT = (-1, initial)
        # 更新時刻, 値
        self.segtree = [self.INT] * (2 * self.n)

    # 区間[l, r)をv(時刻, 値)で更新
    def update(self, l, r, v):
        L, R = l + self.n, r + self.n
        while L < R:
            if L & 1:
                self.segtree[L] = v
                L += 1

            if R & 1:
                self.segtree[R - 1] = v
                R -= 1

            L >>= 1
            R >>= 1

    # i番目の値を取得
    def query(self, i):
        i += self.n
        s = self.INT
        while i > 0:
            s = max(s, self.segtree[i])
            i = i // 2
        return s[1]


N, Q = map(int, input().split())
RUQ = RangeUpdateQuery(N)
for q in range(Q):
    query = list(map(int, sys.stdin.readline().split()))
    if query[0] == 0:
        s, t, x = query[1:]
        RUQ.update(s, t + 1, (q, x))

    if query[0] == 1:
        i = query[1]
        print(RUQ.query(i))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
N, Q = map(int, readline().split())
 
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v
 
        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]
 
 
ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        ans.append(str(query(cmd[0])))
    else:
        s, t, x = cmd
        update(s, t+1, (q, x))
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#INF = 2**31 -1
#n, q = list(map(int, input().split()))
#
#lis = [INF for i in range(n)]
#
#for i in range(q):
#  data = list(map(int, input().split()))
#  if len(data) == 4:
#    a, s, t, x = data
#    for j in range(s, t+1):
#      lis[j] = x
#  else: 
#    b, k = data
#    print(lis[k])



INF = 2**31 - 1
n, q = list(map(int, input().split()))
lazy = [None for i in range(4*n)]
for i in range(n):
  lazy[i] = INF

def updata(a, b, x, k, l, r):
  m = (l+r)//2
  if a >= r or b <= l:
    return 0
  elif a <= l and b >= r:
    lazy[k] = x
  else:
    if lazy[k] != None:
      lazy[k*2+1] = lazy[k]
      lazy[k*2+2] = lazy[k]
      lazy[k] = None
    updata(a, b, x, k*2+1, l, m)
    updata(a, b, x, k*2+2, m, r)

def find(x, k, l, r):
  m = (l+r)//2
  if lazy[k] != None:
    print(lazy[k])
  else:
    if x < (l+r)//2:
      find(x, k*2+1, l, m)
    else:
      find(x, k*2+2, m, r)
      
for i in range(q):
  data = list(map(int, input().split()))
  if len(data) == 4:
    f, a, b, x = data
    updata(a, b+1, x, 0, 0, n)
  else:
    f, i = data
    find(i, 0, 0, n)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]


for i in range(30):#要素数以上の2のベキを見つける
    if n<=1<<i:
        seg_el=1<<i#Segment treeの台の要素数
        break

SEG=[None for i in range(2*seg_el-1)]#Segment tree（遅延伝搬を用いるが、一本のセグ木でOK）

def lazy_update(k,x):#一つ下の子へ伝搬
    if 0<=k<seg_el-1:
        lazy_item,SEG[k]=SEG[k],None
        SEG[k*2+1]=SEG[k*2+2]=lazy_item


def update(a,b,x,k,l,r):
    if SEG[k]!=None:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        lazy_update(k,x)
        
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を更新.後にアクセスされたときに遅延評価する.
        SEG[k]=x#
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)

def getvalue(n):#値を得る
    i=n+seg_el-1
    ANS=SEG[i]
    i=(i-1)//2

    while i>=0:
        if SEG[i]!=None:
            ANS=SEG[i]#できるだけ親に近いノードから値を得るようにする.（そこが最後に更新されたものなので）
        i=(i-1)//2
    return ANS

for i in range(n):
    SEG[i+seg_el-1]=(1<<31)-1

for query in Q:
    if query[0]==0:
        update(query[1],query[2]+1,query[3],0,0,seg_el)
    else:
        print(getvalue(query[1]))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
N, Q = map(int, readline().split())

N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]


ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        ans.append(str(query(cmd[0])))
    else:
        s, t, x = cmd
        update(s, t+1, (q, x))
write("\n".join(ans))
write("\n")

Submission status: Runtime Error

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),min(n-1,(x+1)*b)):a[i]=lazy[x]
    l[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,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: Runtime Error

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),min(n-1,(x+1)*b)):a[i]=lazy[x]
    l[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: Runtime Error

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[x]
    l[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: Runtime Error

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),(min(n-1,(x+1)*b)):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 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: Runtime Error

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),min(n-1,(x+1)*b)):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 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: Runtime Error

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),min(n-1,(x+1)*b)):a[int(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 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: Runtime Error

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),min(n-1,(x+1)*b)):a[i]=l[int(x)]
    l[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: Runtime Error

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),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: Runtime Error

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: Runtime Error

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
            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