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すると思う。試してませんけど。