結果

問題 No.1226 I hate Robot Arms
ユーザー takumi152takumi152
提出日時 2020-09-12 04:17:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,521 ms / 2,000 ms
コード長 6,655 bytes
コンパイル時間 3,187 ms
コンパイル使用メモリ 151,784 KB
実行使用メモリ 78,416 KB
最終ジャッジ日時 2023-08-18 03:28:29
合計ジャッジ時間 38,519 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 4 ms
4,788 KB
testcase_02 AC 402 ms
14,612 KB
testcase_03 AC 521 ms
23,128 KB
testcase_04 AC 645 ms
73,736 KB
testcase_05 AC 582 ms
74,076 KB
testcase_06 AC 1,456 ms
77,888 KB
testcase_07 AC 382 ms
14,312 KB
testcase_08 AC 220 ms
72,064 KB
testcase_09 AC 919 ms
25,288 KB
testcase_10 AC 98 ms
8,536 KB
testcase_11 AC 756 ms
74,028 KB
testcase_12 AC 384 ms
39,224 KB
testcase_13 AC 351 ms
72,948 KB
testcase_14 AC 1,078 ms
26,232 KB
testcase_15 AC 184 ms
71,792 KB
testcase_16 AC 1,443 ms
77,544 KB
testcase_17 AC 365 ms
22,524 KB
testcase_18 AC 232 ms
22,024 KB
testcase_19 AC 759 ms
74,340 KB
testcase_20 AC 701 ms
73,864 KB
testcase_21 AC 903 ms
74,852 KB
testcase_22 AC 1,468 ms
78,116 KB
testcase_23 AC 1,521 ms
78,136 KB
testcase_24 AC 1,445 ms
78,104 KB
testcase_25 AC 1,467 ms
78,416 KB
testcase_26 AC 1,413 ms
78,152 KB
testcase_27 AC 1,410 ms
78,224 KB
testcase_28 AC 1,412 ms
78,064 KB
testcase_29 AC 1,380 ms
78,208 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

struct fenwick_tree {
  int n;
  vector<ll> data;

  fenwick_tree() {
    init(0);
  }

  fenwick_tree(int s) {
    init(s);
  }

  fenwick_tree(vector<ll> &v) {
    int s = v.size();
    init(s);
    for (int i = 0; i < s; i++) add(i, v[i]);
  }

  void init(int s) {
    n = s;
    data = vector<ll>(s);
  }

  void add(int p, ll v) {
    p++;
    while (p <= n) {
      data[p-1] += v;
      p += p & -p;
    }
  }

  ll sum(int l, int r) {
    return sum(r) - sum(l);
  }

  ll sum(int r) {
    ll s = 0;
    while (r > 0) {
      s += data[r-1];
      r -= r & -r;
    }
    return s;
  }
};

struct euclid_lazy_segtree {
  int n;
  vector<vector<double> > data;
  vector<vector<vector<double> > > lazy;
  vector<bool> lazyFlag;

  euclid_lazy_segtree() {
    init(1);
  }

  euclid_lazy_segtree(const int s) {
    init(s);
  }

  euclid_lazy_segtree(const vector<pair<double, double> > &v) {
    int s = v.size();
    init(s);
    for (int i = 0; i < s; i++) {
      data[i+n-1][0] = v[i].first;
      data[i+n-1][1] = v[i].second;
    }
  }

  void init(const int s) {
    n = 1;
    while (n < s) n <<= 1;
    data = vector<vector<double> >(2*n-1, vector<double>({0.0, 0.0, 1.0}));
    lazy = vector<vector<vector<double> > >(2*n-1, vector<vector<double> >(3, vector<double>(3)));
    for (int i = 0; i < 2*n-1; i++) {
      for (int j = 0; j < 3; j++) lazy[i][j][j] = 1.0;
    }
    lazyFlag = vector<bool>(2*n-1);
  }

  void apply_op(vector<vector<double> > &op, vector<vector<double> > &to) {
    evaluate_lazy(op, to);
  }

  void evaluate_lazy(vector<vector<double> > &op, vector<vector<double> > &to) {
    static vector<vector<double> > next(3, vector<double>(3));
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        next[i][j] = 0.0;
        for (int k = 0; k < 3; k++) {
          next[i][j] += op[i][k] * to[k][j];
        }
      }
    }
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        to[i][j] = next[i][j];
      }
    }
  }

  void evaluate_data(vector<vector<double> > &op, vector<double> &to) {
    static vector<double> next(3);
    for (int i = 0; i < 3; i++) {
      next[i] = 0.0;
      for (int k = 0; k < 3; k++) {
        next[i] += op[i][k] * to[k];
      }
    }
    for (int i = 0; i < 3; i++) {
      to[i] = next[i];
    }
  }

  void propagate(int p, int a, int b) {
    if (lazyFlag[p]) {
      if (b - a > 1) {
        evaluate_lazy(lazy[p], lazy[p*2+1]);
        evaluate_lazy(lazy[p], lazy[p*2+2]);
        lazyFlag[p*2+1] = true;
        lazyFlag[p*2+2] = true;
      }
      else {
        evaluate_data(lazy[p], data[p]);
      }
      for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
          lazy[p][i][j] = (i == j ? 1.0 : 0.0);
        }
      }
      lazyFlag[p] = false;
    }
  }

  void update(int l, int r, vector<vector<double> > op, int p = 0, int a = 0, int b = -1) {
    if (b < 0) b = n; // init

    // propagate lazy value
    propagate(p, a, b);

    if (r <= a || b <= l) return; // out of range
    if (l <= a && b <= r) { // fully covered
      evaluate_lazy(op, lazy[p]);
      lazyFlag[p] = true;
      propagate(p, a, b);
    }
    else {
      update(l, r, op, p*2+1, a, (a + b) / 2); // left
      update(l, r, op, p*2+2, (a + b) / 2, b); // right
    }
    return;
  }

  void translate(int l, int r, double x, double y) {
    vector<vector<double> > op({{1.0, 0.0,   x},
                                {0.0, 1.0,   y},
                                {0.0, 0.0, 1.0}});

    update(l, r, op);
  }

  void rotate_with_pivot(int l, int r, double x, double y, double theta) {
    vector<vector<double> > op1({{1.0, 0.0,  -x},
                                 {0.0, 1.0,  -y},
                                 {0.0, 0.0, 1.0}});
    vector<vector<double> > op2({{cos(theta), -sin(theta), 0.0},
                                 {sin(theta),  cos(theta), 0.0},
                                 {       0.0,         0.0, 1.0}});
    vector<vector<double> > op3({{1.0, 0.0,   x},
                                 {0.0, 1.0,   y},
                                 {0.0, 0.0, 1.0}});
    vector<vector<double> > op({{1.0, 0.0, 0.0},
                                {0.0, 1.0, 0.0},
                                {0.0, 0.0, 1.0}});

    apply_op(op1, op);
    apply_op(op2, op);
    apply_op(op3, op);
    update(l, r, op);
  }

  pair<double, double> query(int l, int r, int p = 0, int a = 0, int b = -1) {
    if (b < 0) b = n; // init
    if (r <= a || b <= l) return pair<double, double>(0.0, 0.0); // out of range

    // propagate lazy value
    propagate(p, a, b);

    if (l <= a && b <= r) return pair<double, double>(data[p][0] / data[p][2], data[p][1] / data[p][2]); // fully covered

    pair<double, double> vl = query(l, r, p*2+1, a, (a + b) / 2); // left
    pair<double, double> vr = query(l, r, p*2+2, (a + b) / 2, b); // right
    return pair<double, double>(vl.first + vr.first, vl.second + vr.second);
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, q;
  cin >> n >> q;
  vector<vector<ll> > query(q, vector<ll>(3));
  for (auto &x: query) {
    cin >> x[0] >> x[1];
    if (x[0] != 2) cin >> x[2];
  }

  vector<pair<double, double> > init_pos(n+1);
  for (int i = 0; i < n+1; i++) init_pos[i].first = 1.0 * i;
  euclid_lazy_segtree elst(init_pos);

  vector<int> length(n, 1);
  fenwick_tree angle(n);
  vector<pair<double, double> > ans;
  for (auto &x: query) {
    if (x[0] == 0) {
      double delta = (double) (x[2] - angle.sum(x[1]-1, x[1])) * 3.141592653589793238462643383 / 180.0;
      auto pos = elst.query(x[1]-1, x[1]);
      elst.rotate_with_pivot(x[1], n+1, pos.first, pos.second, delta);
      angle.add(x[1]-1, x[2] - angle.sum(x[1]-1, x[1]));
    }
    else if (x[0] == 1) {
      double theta = (double) (angle.sum(0, x[1]) % 360) * 3.141592653589793238462643383 / 180.0;
      int delta = x[2] - length[x[1]-1];
      elst.translate(x[1], n+1, (double) delta * cos(theta), (double) delta * sin(theta));
      length[x[1]-1] = x[2];
    }
    else if (x[0] == 2) {
      ans.push_back(elst.query(x[1], x[1]+1));
    }
  }

  for (auto &x: ans) cout << fixed << setprecision(20) << x.first << " " << fixed << setprecision(20) << x.second << endl;

  return 0;
}
0