結果
問題 | No.1226 I hate Robot Arms |
ユーザー | betrue12 |
提出日時 | 2020-09-11 22:50:14 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 544 ms / 2,000 ms |
コード長 | 6,381 bytes |
コンパイル時間 | 2,465 ms |
コンパイル使用メモリ | 215,356 KB |
実行使用メモリ | 22,152 KB |
最終ジャッジ日時 | 2023-08-30 10:13:53 |
合計ジャッジ時間 | 18,138 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 151 ms
5,964 KB |
testcase_03 | AC | 193 ms
8,000 KB |
testcase_04 | AC | 221 ms
21,104 KB |
testcase_05 | AC | 195 ms
21,588 KB |
testcase_06 | AC | 521 ms
21,680 KB |
testcase_07 | AC | 147 ms
5,720 KB |
testcase_08 | AC | 55 ms
21,452 KB |
testcase_09 | AC | 351 ms
7,800 KB |
testcase_10 | AC | 39 ms
4,388 KB |
testcase_11 | AC | 247 ms
21,096 KB |
testcase_12 | AC | 131 ms
12,144 KB |
testcase_13 | AC | 100 ms
21,632 KB |
testcase_14 | AC | 414 ms
7,824 KB |
testcase_15 | AC | 32 ms
21,324 KB |
testcase_16 | AC | 526 ms
21,660 KB |
testcase_17 | AC | 134 ms
7,884 KB |
testcase_18 | AC | 85 ms
8,068 KB |
testcase_19 | AC | 257 ms
21,364 KB |
testcase_20 | AC | 243 ms
21,092 KB |
testcase_21 | AC | 319 ms
21,264 KB |
testcase_22 | AC | 525 ms
22,056 KB |
testcase_23 | AC | 544 ms
22,100 KB |
testcase_24 | AC | 527 ms
22,056 KB |
testcase_25 | AC | 537 ms
22,088 KB |
testcase_26 | AC | 507 ms
22,096 KB |
testcase_27 | AC | 524 ms
22,072 KB |
testcase_28 | AC | 534 ms
22,152 KB |
testcase_29 | AC | 526 ms
22,112 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; const double PI = acos(-1); template<typename T> struct BIT { int n; vector<T> dat; BIT(int n=0){ initialize(n); } void initialize(int nin){ n = nin; dat.assign(n, 0); } T sum(int i){ T s = 0; while(i >= 0){ s += dat[i]; i = (i & (i+1)) - 1; } return s; } T sum_between(int i, int j){ return sum(j) - sum(i-1); } void plus(int i, T x){ while(i < n){ dat[i] += x; i |= i+1; } } // a[0]+...+a[ret] >= x int lower_bound(T x){ if(x < 0) return -1; int ret = -1; int k = 1; while(2*k <= n) k <<= 1; for( ;k>0; k>>=1){ if(ret+k < n && dat[ret+k] < x){ x -= dat[ret+k]; ret += k; } } return ret + 1; } }; template<typename F, typename T, typename Func_mf, typename Func_op, typename Func_mv> struct LazySegtree { int n, n_org; vector<T> dat; vector<F> laz; Func_mf merge_functions; Func_op operate; Func_mv merge_values; F fe; T te; LazySegtree(){} LazySegtree(int n_org, Func_mf merge_functions, Func_op operate, Func_mv merge_values, F fe, T te): n_org(n_org), merge_functions(merge_functions), operate(operate), merge_values(merge_values), fe(fe), te(te){ n = 1; while(n < n_org) n <<= 1; dat.assign(2*n-1, te); laz.assign(2*n-1, fe); } void build(vector<T>& A){ for(int k=0; k<int(A.size()); k++) dat[k+n-1] = A[k]; for(int k=n-2; k>=0; k--) dat[k] = merge_values(dat[2*k+1], dat[2*k+2]); } void eval(int k, int w){ if(laz[k] == fe) return; operate(dat[k], laz[k], w); if(k < n-1){ merge_functions(laz[2*k+1], laz[k]); merge_functions(laz[2*k+2], laz[k]); } laz[k] = fe; } void update_between(int a, int b, F x){ update(a, b+1, x, 0, 0, n); } void update(int a, int b, F x, int k, int lb, int rb){ eval(k, rb-lb); if(b <= lb || rb <= a) return; if(a <= lb && rb <= b){ merge_functions(laz[k], x); eval(k, rb-lb); }else{ int mb = (lb+rb)>>1; update(a, b, x, 2*k+1, lb, mb); update(a, b, x, 2*k+2, mb, rb); dat[k] = merge_values(dat[2*k+1], dat[2*k+2]); } } T get_between(int a, int b){ return query(a, b+1, 0, 0, n); } T query(int a, int b, int k, int lb, int rb){ eval(k, rb-lb); if(rb<=a || b<=lb) return te; if(a<=lb && rb<=b) return dat[k]; int mb = (lb+rb)>>1; T vl = query(a, b, 2*k+1, lb, mb); T vr = query(a, b, 2*k+2, mb, rb); return merge_values(vl, vr); } }; using MA = array<array<double, 2>, 2>; using MB = array<array<double, 1>, 2>; MB matmulAB(MA A, MB B){ assert(A[0].size() == B.size()); int N = A.size(), M = B[0].size(), K = B.size(); MB ans; for(int i=0; i<N; i++) for(int j=0; j<M; j++) ans[i][j] = 0.0; for(int i=0; i<N; i++) for(int j=0; j<M; j++) for(int k=0; k<K; k++) ans[i][j] += A[i][k] * B[k][j]; return ans; } MA matmulAA(MA A, MA B){ assert(A[0].size() == B.size()); int N = A.size(), M = B[0].size(), K = B.size(); MA ans; for(int i=0; i<N; i++) for(int j=0; j<M; j++) ans[i][j] = 0.0; for(int i=0; i<N; i++) for(int j=0; j<M; j++) for(int k=0; k<K; k++) ans[i][j] += A[i][k] * B[k][j]; return ans; } MB matadd(MB A, MB B){ int N = A.size(), M = A[0].size(); for(int i=0; i<N; i++) for(int j=0; j<M; j++) A[i][j] += B[i][j]; return A; } MA make_E22(){ MA E22; E22[0][0] = E22[1][1] = 1.0; E22[0][1] = E22[1][0] = 0.0; return E22; } MB make_Z21(){ MB Z21; Z21[0][0] = Z21[1][0] = 0.0; return Z21; } MA E22 = make_E22(); MB Z21 = make_Z21(); auto make_segtree = [](int N){ using F = pair<MA, MB>; using T = MB; auto merge_functions = [](F& f, F& g){ f.first = matmulAA(g.first, f.first); f.second = matadd(matmulAB(g.first, f.second), g.second); }; auto operate = [](T& v, F& f, int w){ v = matadd(matmulAB(f.first, v), f.second); }; auto merge_values = [](T& a, T& b){ return a == Z21 ? b : a; }; F fe = {E22, Z21}; T te = Z21; return LazySegtree<F, T, decltype(merge_functions), decltype(operate), decltype(merge_values)> (N, merge_functions, operate, merge_values, fe, te); }; int main(){ int N, Q; cin >> N >> Q; auto st = make_segtree(N+1); vector<int> L(N, 1); BIT<int> Theta(N); auto calc = [&](int deg, MB pos)->pair<MA, MB>{ double theta = deg*PI/180; double x0 = pos[0][0], y0 = pos[1][0]; MA a; a[0][0] = a[1][1] = cos(theta); a[0][1] = -sin(theta); a[1][0] = sin(theta); MB b; b[0][0] = -cos(theta)*x0 + sin(theta)*y0 + x0; b[1][0] = -sin(theta)*x0 - cos(theta)*y0 + y0; return {a, b}; }; vector<MB> ini(N+1); for(int i=0; i<=N; i++){ ini[i][0][0] = double(i); ini[i][1][0] = 0.0; } st.build(ini); while(Q--){ int t; scanf("%d", &t); if(t == 1){ int i, x; scanf("%d %d", &i, &x); i--; int d = x - L[i]; int theta = Theta.sum(i) % 360; MB diff; diff[0][0] = d*cos(theta*PI/180); diff[1][0] = d*sin(theta*PI/180); st.update_between(i+1, N, {E22, diff}); L[i] = x; }else if(t == 0){ int i, x; scanf("%d %d", &i, &x); i--; auto pos = st.get_between(i, i); int diff = x - Theta.sum_between(i, i); auto f = calc(diff, pos); st.update_between(i+1, N, f); Theta.plus(i, diff); }else{ int i; scanf("%d", &i); auto ans = st.get_between(i, i); printf("%.10lf %.10lf\n", ans[0][0], ans[1][0]); } } return 0; }