結果
| 問題 |
No.1226 I hate Robot Arms
|
| コンテスト | |
| ユーザー |
 risujiroh
|
| 提出日時 | 2020-09-11 22:36:06 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,026 ms / 2,000 ms |
| コード長 | 6,433 bytes |
| コンパイル時間 | 2,858 ms |
| コンパイル使用メモリ | 261,008 KB |
| 最終ジャッジ日時 | 2025-01-14 10:57:50 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
#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) {
num::value_type x;
cin >> x;
auto th = get_arg(i);
seg.act(i, n, {1, -polar(get_len(i), th)});
seg.act(i, n, {1, +polar(x, th)});
} else if (t == 2) {
auto z = seg.get(i).z;
cout << real(z) << ' ' << imag(z) << '\n';
} else
assert(false);
}
}