結果
問題 | No.1932 動く点 P / Moving Point P |
ユーザー | ああいい |
提出日時 | 2022-05-08 12:56:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,729 ms / 6,000 ms |
コード長 | 2,363 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 87,084 KB |
実行使用メモリ | 160,196 KB |
最終ジャッジ日時 | 2023-09-22 08:22:36 |
合計ジャッジ時間 | 43,769 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 82 ms
72,080 KB |
testcase_01 | AC | 1,398 ms
141,944 KB |
testcase_02 | AC | 926 ms
139,116 KB |
testcase_03 | AC | 1,994 ms
91,360 KB |
testcase_04 | AC | 2,405 ms
104,352 KB |
testcase_05 | AC | 2,165 ms
103,740 KB |
testcase_06 | AC | 521 ms
112,260 KB |
testcase_07 | AC | 3,576 ms
158,356 KB |
testcase_08 | AC | 3,729 ms
160,196 KB |
testcase_09 | AC | 2,747 ms
158,696 KB |
testcase_10 | AC | 2,694 ms
158,964 KB |
testcase_11 | AC | 2,707 ms
158,988 KB |
ソースコード
import copy def seki(x,y): l = [[0] * 3 for _ in range(3)] for i in range(3): for j in range(3): for k in range(3): l[i][j] += x[i][k] * y[k][j] return l e = [[0] * 3 for _ in range(3)] for i in range(3): e[i][i] = 1 class SegTree: #単位元と結合演算はここ変える #いろんな種類のsegは作れないかも #→changeで変えれる unit = copy.deepcopy(e) def f(self,x,y): return seki(x,y) #頂点は1-index、一番下の段は0-index(bitは1-index) def __init__(self,N): self.N = N self.X = [self.unit] * (N + N) def build(self,seq): for i,x in enumerate(seq,self.N): self.X[i] = x for i in range(self.N-1,0,-1): self.X[i] = self.f(self.X[i << 1],self.X[i << 1 | 1]) def set(self,i,x): i += self.N self.X[i] = x while i > 1: i >>= 1 self.X[i] = self.f(self.X[i << 1],self.X[i << 1 | 1]) def fold(self,L,R): #区間[L,R)についてfold #0 <= L,R <= N にしなきゃダメ L += self.N R += self.N vL = self.unit vR = self.unit while L < R: if L & 1: vL = self.f(vL,self.X[L]) L += 1 if R & 1: R -= 1 vR = self.f(self.X[R],vR) L >>= 1 R >>= 1 return self.f(vL,vR) def change(self,f,unit): self.f = f self.unit = unit from math import cos,sin,pi,radians def mat(x,y): l = [[1,0,x], [0,1,y], [0,0,1]] return l def rot(r): u = radians(r) l = [[cos(u),-sin(u),0], [sin(u),cos(u),0], [0,0,1]] return l N = int(input()) seg = SegTree(N) seq = [None] * N for _ in range(N): p,q,r = map(float,input().split()) t = seki(mat(p,q),rot(r)) t = seki(t,mat(-p,-q)) seq[N - 1 - _] = t seg.build(seq) Q = int(input()) def seki2(l,x,y): ans = [0] * 3 u = [x,y,1] for i in range(3): for j in range(3): ans[i] += l[i][j] * u[j] return ans for _ in range(Q): s,t,x,y = map(float,input().split()) s = int(s) s = N - s t = int(t) t = N - t l = seg.fold(t,s + 1) ans = seki2(l,x,y) print(ans[0],ans[1])