結果

問題 No.1226 I hate Robot Arms
ユーザー takumi152takumi152
提出日時 2020-09-12 04:05:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,774 bytes
コンパイル時間 1,497 ms
コンパイル使用メモリ 129,984 KB
実行使用メモリ 84,556 KB
最終ジャッジ日時 2024-06-10 11:37:47
合計ジャッジ時間 11,674 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,884 KB
testcase_01 AC 4 ms
6,940 KB
testcase_02 AC 1,091 ms
14,720 KB
testcase_03 AC 1,543 ms
23,296 KB
testcase_04 AC 1,709 ms
73,708 KB
testcase_05 AC 1,472 ms
74,212 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 evaluate_lazy(vector<vector<double> > &op, vector<vector<double> > &to) {
    vector<vector<double> > next(3, vector<double>(3));
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        for (int k = 0; k < 3; k++) {
          next[i][j] += op[i][k] * to[k][j];
        }
      }
    }
    to = next;
  }

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

  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]);
      }
      lazy[p] = vector<vector<double> >(3, vector<double>(3));
      for (int i = 0; i < 3; i++) lazy[p][i][i] = 1.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(3, vector<double>(3));
    for (int i = 0; i < 3; i++) op[i][i] = 1.0;

    op[0][2] = x;
    op[1][2] = y;

    update(l, r, op);
  }

  void rotate_with_pivot(int l, int r, double x, double y, double theta) {
    vector<vector<double> > op(3, vector<double>(3));
    for (int i = 0; i < 3; i++) {
      op[i][i] = 1.0;
    }

    op[0][0] = cos(theta);
    op[0][1] = -sin(theta);
    op[1][0] = sin(theta);
    op[1][1] = cos(theta);

    translate(l, r, -x, -y);
    update(l, r, op);
    translate(l, r, x, y);
  }

  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