結果
問題 | No.1226 I hate Robot Arms |
ユーザー |
|
提出日時 | 2020-09-11 21:49:51 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,874 ms / 2,000 ms |
コード長 | 6,676 bytes |
コンパイル時間 | 4,727 ms |
コンパイル使用メモリ | 89,652 KB |
実行使用メモリ | 148,108 KB |
最終ジャッジ日時 | 2024-12-31 11:42:29 |
合計ジャッジ時間 | 46,429 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
package contest200911;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.InputMismatchException;public class D {InputStream is;PrintWriter out;String INPUT = "";void solve(){int n = ni();SegmentTreeMatrix st = new SegmentTreeMatrix(n);int[] ls = new int[n];double[] xs = new double[n];Arrays.fill(ls, 1);for(int Q = ni(); Q> 0;Q--){int t = ni();if(t == 0){int i = ni();double x = ni()/180.*Math.PI;xs[i-1] = x;double cx = Math.cos(xs[i-1]);double sx = Math.sin(xs[i-1]);double[][] M = st.node[st.H+i-1];M[2][2] = cx; M[2][3] = -sx;M[3][2] = sx; M[3][3] = cx;M[0][2] = ls[i-1]*cx; M[0][3] = ls[i-1]*-sx;M[1][2] = ls[i-1]*sx; M[1][3] = ls[i-1]*cx;st.update(i-1);}else if(t == 1){int i = ni();int x = ni();ls[i-1] = x;double cx = Math.cos(xs[i-1]);double sx = Math.sin(xs[i-1]);double[][] M = st.node[st.H+i-1];M[2][2] = cx; M[2][3] = -sx;M[3][2] = sx; M[3][3] = cx;M[0][2] = ls[i-1]*cx; M[0][3] = ls[i-1]*-sx;M[1][2] = ls[i-1]*sx; M[1][3] = ls[i-1]*cx;st.update(i-1);}else{int i = ni();double[] res = st.apply(0, i, new double[]{0, 0, 1, 0});out.printf("%.14f %.14f\n", res[0], res[1]);}}}//// (cos x -sin x)// (sin x cos x)public static class SegmentTreeMatrix {public int M, H, N;public double[][][] node;public static int mod = 1000000007;public static long BIG = 8L*mod*mod;public static int S = 4;public SegmentTreeMatrix(int n){N = n;M = Integer.highestOneBit(Math.max(N-1, 1))<<2;H = M>>>1;node = new double[M][][];for(int i = 0;i < N;i++){node[H+i] = new double[S][S];for(int j = 0;j < 4;j++){node[H+i][j][j] = 1;}node[H+i][0][2] = 1;node[H+i][1][3] = 1;}for(int i = H-1;i >= 1;i--)propagate(i);}private void propagate(int cur){node[cur] = prop2(node[2*cur], node[2*cur+1], node[cur]);}private double[][] prop2(double[][] L, double[][] R, double[][] C){if(L != null && R != null){C = mul(R, L, C);return C;}else if(L != null){return prop1(L, C);}else if(R != null){return prop1(R, C);}else{return null;}}private double[][] prop1(double[][] L, double[][] C){if(C == null){// C = L; // read onlyC = new double[S][];for(int i = 0;i < S;i++){C[i] = Arrays.copyOf(L[i], S);}}else{for(int i = 0;i < S;i++){C[i] = Arrays.copyOf(L[i], S);}}return C;}public void update(int pos) {for(int i = H+pos>>>1;i >= 1;i>>>=1)propagate(i);}public double[] apply(int l, int r, double[] v){return apply(l, r, 0, H, 1, v);}protected double[] apply(int l, int r, int cl, int cr, int cur, double[] v){if(l <= cl && cr <= r){return mul(node[cur], v);}else{int mid = cl+cr>>>1;if(cl < r && l < mid){v = apply(l, r, cl, mid, 2*cur, v);}if(mid < r && l < cr){v = apply(l, r, mid, cr, 2*cur+1, v);}return v;}}public static double[] mul(double[][] A, double[] v){int m = A.length;int n = v.length;double[] w = new double[m];for(int i = 0;i < m;i++){double sum = 0;for(int k = 0;k < n;k++){sum += A[i][k] * v[k];}w[i] = sum;}return w;}public static double[][] mul(double[][] A, double[][] B, double[][] C){assert A[0].length == B.length;int m = A.length;int n = A[0].length;int o = B[0].length;if(C == null){C = new double[m][o];}else{for(int i = 0;i < m;i++){Arrays.fill(C[i], 0.);}}for(int i = 0;i < m;i++){for(int k = 0;k < n;k++){for(int j = 0;j < o;j++){C[i][j] += A[i][k] * B[k][j];}}}return C;}}void run() throws Exception{is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);long s = System.currentTimeMillis();solve();out.flush();if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){// @Override// public void run() {// long s = System.currentTimeMillis();// solve();// out.flush();// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// }// };// t.start();// t.join();}public static void main(String[] args) throws Exception { new D().run(); }private byte[] inbuf = new byte[1024];public int lenbuf = 0, ptrbuf = 0;private int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private double nd() { return Double.parseDouble(ns()); }private char nc() { return (char)skip(); }private String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')sb.appendCodePoint(b);b = readByte();}return sb.toString();}private char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private long[] nal(int n){long[] a = new long[n];for(int i = 0;i < n;i++)a[i] = nl();return a;}private char[][] nm(int n, int m) {char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private int[][] nmi(int n, int m) {int[][] map = new int[n][];for(int i = 0;i < n;i++)map[i] = na(m);return map;}private int ni() { return (int)nl(); }private long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }}