読者です 読者をやめる 読者になる 読者になる

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #344 (Div.2)

はい。
http://codeforces.com/contest/631

A. Interview

ざっくりと大意

・数列a,bをl,rで区切って区間内のそれぞれのOR(論理和)の最大値はいくつか?

Python2

n=int(raw_input())
def sol(l):
    x='|'.join(l)
    return eval(x)
a=map(str,raw_input().split())
b=map(str,raw_input().split())
print sol(a)+sol(b)

l,r区間を縮めたり広げたり調節する必要はなく全区間論理和の対象にしてしまえば良い。最小の区間で〜とかの制限はないのですべての値を使って良いと思う。

B. Print Check

ざっくりと大意

・n * mの領域が初期値0で埋まっているのをk件のクエリで色塗りする。
・クエリの初項が1なら行に対するクエリ。2項目の行を3項目の色で塗る。
・初項が2なら列に対するクエリ。2項目の列を3項目の色で塗る。

Python2

n,m,k=map(int,raw_input().split())
R=[-1]*n
C=[-1]*m
Q=[]
ans=chk=0
for i in range(k):
    p,q,a=map(int,raw_input().split())
    if p==1:
        if R[q-1]!=-1:
            Q[R[q-1]]=[0]
        R[q-1]=i
    else:
        if C[q-1]!=-1:
            Q[C[q-1]]=[0]
        C[q-1]=i
    Q.append([p,q,a])
l=[[0]*m for _ in range(n)]
for i in Q:
    if i[0]==1:
        l[i[1]-1]=[i[2]]*m
    elif i[0]==2:
        for j in range(n):
            l[j][i[1]-1]=i[2]
for i in l:
    print ' '.join(map(str,i))

クエリは一度全部受け取ってから塗ることにした。同じ行or列に対するクエリは最新のものだけ保存するようにした。圧縮したクエリを先頭から処理して出力した。n,mのそれぞれの最大値は5000があり得るが、n * mが最大でも100000らしい。なので例えば最大の広さは5000行 * 200列とかになる。それに対してクエリが最大100000件なので、毎クエリ塗ってたらTLEすると思う。試してませんけど。