結果

問題 No.1226 I hate Robot Arms
ユーザー risujirohrisujiroh
提出日時 2020-09-11 22:32:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,048 ms / 2,000 ms
コード長 6,380 bytes
コンパイル時間 4,595 ms
コンパイル使用メモリ 271,896 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-07-19 23:30:29
合計ジャッジ時間 31,733 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 301 ms
5,376 KB
testcase_03 AC 363 ms
6,656 KB
testcase_04 AC 410 ms
13,312 KB
testcase_05 AC 360 ms
15,564 KB
testcase_06 AC 980 ms
14,956 KB
testcase_07 AC 280 ms
5,632 KB
testcase_08 AC 87 ms
13,568 KB
testcase_09 AC 686 ms
6,272 KB
testcase_10 AC 74 ms
5,376 KB
testcase_11 AC 449 ms
12,640 KB
testcase_12 AC 252 ms
8,576 KB
testcase_13 AC 179 ms
15,676 KB
testcase_14 AC 841 ms
6,784 KB
testcase_15 AC 51 ms
14,464 KB
testcase_16 AC 976 ms
15,988 KB
testcase_17 AC 257 ms
7,424 KB
testcase_18 AC 171 ms
7,808 KB
testcase_19 AC 453 ms
13,908 KB
testcase_20 AC 428 ms
13,036 KB
testcase_21 AC 613 ms
12,160 KB
testcase_22 AC 1,037 ms
16,116 KB
testcase_23 AC 1,042 ms
16,256 KB
testcase_24 AC 1,048 ms
16,252 KB
testcase_25 AC 1,035 ms
16,296 KB
testcase_26 AC 1,010 ms
16,232 KB
testcase_27 AC 1,008 ms
16,112 KB
testcase_28 AC 991 ms
16,384 KB
testcase_29 AC 993 ms
16,256 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/extc++.h>

struct segment_tree_base {
  virtual int size() const = 0;

 protected:
  template <class F>
  void forward(int l, int r, F f) const {
    int h = h1(l += size() - 1, r += size());
    for (int s = 0; s < h; ++s)
      if (int i = l >> s; ~i & 1) f(i + 1);
    for (int s = h; s--;)
      if (int i = r >> s; i & 1) f(i - 1);
  }
  template <class F>
  void forward(int l, int r, F f) {
    const_cast<const segment_tree_base*>(this)->forward(l, r, f);
  }
  template <class F>
  void backward(int l, int r, F f) const {
    int h = h1(l += size() - 1, r += size());
    for (int s = 0; s < h; ++s)
      if (int i = r >> s; i & 1) f(i - 1);
    for (int s = h; s--;)
      if (int i = l >> s; ~i & 1) f(i + 1);
  }
  template <class F>
  void backward(int l, int r, F f) {
    const_cast<const segment_tree_base*>(this)->backward(l, r, f);
  }
  template <class F>
  void downward(int l, int r, F f) const {
    if (l == r or (l == 0 and r == size())) return;
    int h = h2(l += size(), r += size());
    for (int s = std::__lg(l); s > h; --s) f(l >> s);
    for (int s = h; s > __builtin_ctz(l); --s) f(l >> s);
    for (int s = h; s > __builtin_ctz(r); --s) f(r >> s);
  }
  template <class F>
  void downward(int l, int r, F f) {
    const_cast<const segment_tree_base*>(this)->downward(l, r, f);
  }
  template <class F>
  void upward(int l, int r, F f) const {
    if (l == r or (l == 0 and r == size())) return;
    int h = h2(l += size(), r += size());
    for (int s = __builtin_ctz(r); s++ < h;) f(r >> s);
    for (int s = __builtin_ctz(l); s++ < h;) f(l >> s);
    for (int s = h; s++ < std::__lg(l);) f(l >> s);
  }
  template <class F>
  void upward(int l, int r, F f) {
    const_cast<const segment_tree_base*>(this)->upward(l, r, f);
  }

 private:
  static int h1(int l, int r) {
    for (int h = 0;; ++h)
      if ((r >> h) - (l >> h) == 1) return h;
  }
  static int h2(int l, int r) {
    l <<= std::__lg(l) < std::__lg(r);
    return std::__lg(l ^ r);
  }
};

template <class T, class Action>
struct lazy_segment_tree : segment_tree_base {
  lazy_segment_tree() {}
  template <class Generator>
  lazy_segment_tree(int n, Generator gen) : tree(2 * n), lazy(n) {
    for (int i = 0; i < n; ++i) tree[n + i] = gen(i);
    for (int i = n; i-- > 1;) pull(i);
  }

  int size() const override { return std::size(lazy); }
  T fold(int l, int r) {
    assert(0 <= l), assert(l <= r), assert(r <= size());
    downward(l, r, [&](int i) { push(i); });
    T res{};
    forward(l, r, [&](int i) { res = res * tree[i]; });
    return res;
  }
  T get(int i) {
    assert(0 <= i), assert(i < size());
    return fold(i, i + 1);
  }
  T fold_all_rotated() const { return size() ? tree[1] : T{}; }
  template <class Function>
  void update(int i, Function func) {
    assert(0 <= i), assert(i < size());
    downward(i, i + 1, [&](int j) { push(j); });
    tree[size() + i] = func(tree[size() + i]);
    upward(i, i + 1, [&](int j) { pull(j); });
  }
  void act(int l, int r, const Action& f) {
    assert(0 <= l), assert(l <= r), assert(r <= size());
    downward(l, r, [&](int i) { push(i); });
    forward(l, r, [&](int i) { apply(i, f); });
    upward(l, r, [&](int i) { pull(i); });
  }
  template <class Predicate>
  int forward_search(int l, int r, Predicate pred) {
    assert(0 <= l), assert(l <= r), assert(r <= size());
    downward(l, r, [&](int i) { push(i); });
    T a{};
    assert(pred(a));
    int res = r;
    forward(l, r, [&](int i) {
      if (res < r) return;
      if (T na = a * tree[i]; pred(na)) {
        a = na;
        return;
      }
      while (i < size()) {
        push(i);
        if (T na = a * tree[i *= 2]; pred(na)) a = na, ++i;
      }
      res = i - size();
    });
    return res;
  }
  template <class Predicate>
  int backward_search(int l, int r, Predicate pred) {
    assert(0 <= l), assert(l <= r), assert(r <= size());
    downward(l, r, [&](int i) { push(i); });
    T a{};
    assert(pred(a));
    int res = l - 1;
    backward(l, r, [&](int i) {
      if (res >= l) return;
      if (T na = a * tree[i]; pred(na)) {
        a = na;
        return;
      }
      while (i < size()) {
        push(i);
        if (T na = a * tree[i = 2 * i + 1]; pred(na)) a = na, --i;
      }
      res = i - size();
    });
    return res;
  }

 private:
  std::vector<T> tree;
  std::vector<Action> lazy;

  void apply(int i, const Action& f) {
    tree[i] = f(tree[i]);
    if (i < size()) lazy[i] = lazy[i] * f;
  }
  void push(int i) {
    apply(2 * i, lazy[i]), apply(2 * i + 1, lazy[i]);
    lazy[i] = Action{};
  }
  void pull(int i) { tree[i] = tree[2 * i] * tree[2 * i + 1]; }
};

using num = std::complex<long double>;

struct node {
  num z;
  friend node operator*(const node& a, const node& b) { return {a.z + b.z}; }
};
struct action {
  num a = 1, b;
  node operator()(const node& x) const { return {x.z * a + b}; }
  friend action operator*(const action& f, const action& g) {
    return {f.a * g.a, f.b * g.a + g.b};
  }
};

int main() {
  using namespace std;
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);

  int n, q;
  cin >> n >> q;

  lazy_segment_tree<node, action> seg(n, [](int i) -> node { return {i + 1}; });
  auto get_len = [&](int i) {
    num d = seg.get(i).z - (i ? seg.get(i - 1).z : 0);
    return abs(d);
  };
  auto get_arg = [&](int i) -> num::value_type {
    if (i == -1) return 0;
    num d = seg.get(i).z - (i ? seg.get(i - 1).z : 0);
    return arg(d);
  };

  while (q--) {
    int t, i;
    cin >> t >> i;
    --i;
    if (t == 0) {
      num::value_type x;
      cin >> x;
      x /= 180;
      x *= acos(num::value_type(-1));
      num off = i ? seg.get(i - 1).z : 0;
      auto th = get_arg(i - 1) + x - get_arg(i);
      seg.act(i, n, {1, -off});
      seg.act(i, n, {polar(num::value_type(1), th), 0});
      seg.act(i, n, {1, +off});
    } else if (t == 1) {
      int x;
      cin >> x;
      auto d = polar(x - get_len(i), get_arg(i));
      seg.act(i, n, {1, d});
    } else if (t == 2) {
      auto z = seg.get(i).z;
      cout << real(z) << ' ' << imag(z) << '\n';
    } else
      assert(false);
  }
}
0