結果
問題 | No.1226 I hate Robot Arms |
ユーザー | 👑 hitonanode |
提出日時 | 2020-09-12 00:40:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,293 ms / 2,000 ms |
コード長 | 3,480 bytes |
コンパイル時間 | 11,479 ms |
コンパイル使用メモリ | 424,604 KB |
実行使用メモリ | 39,272 KB |
最終ジャッジ日時 | 2023-08-30 11:17:42 |
合計ジャッジ時間 | 32,395 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 10 ms
4,376 KB |
testcase_01 | AC | 10 ms
4,380 KB |
testcase_02 | AC | 395 ms
6,888 KB |
testcase_03 | AC | 408 ms
11,892 KB |
testcase_04 | AC | 470 ms
30,200 KB |
testcase_05 | AC | 437 ms
37,580 KB |
testcase_06 | AC | 1,102 ms
35,328 KB |
testcase_07 | AC | 344 ms
8,432 KB |
testcase_08 | AC | 113 ms
31,316 KB |
testcase_09 | AC | 826 ms
10,772 KB |
testcase_10 | AC | 91 ms
6,120 KB |
testcase_11 | AC | 535 ms
28,912 KB |
testcase_12 | AC | 278 ms
17,204 KB |
testcase_13 | AC | 219 ms
37,920 KB |
testcase_14 | AC | 989 ms
11,972 KB |
testcase_15 | AC | 80 ms
34,068 KB |
testcase_16 | AC | 1,096 ms
38,200 KB |
testcase_17 | AC | 312 ms
14,180 KB |
testcase_18 | AC | 193 ms
14,864 KB |
testcase_19 | AC | 550 ms
32,512 KB |
testcase_20 | AC | 483 ms
29,716 KB |
testcase_21 | AC | 682 ms
27,188 KB |
testcase_22 | AC | 1,197 ms
39,196 KB |
testcase_23 | AC | 1,183 ms
39,184 KB |
testcase_24 | AC | 1,178 ms
39,108 KB |
testcase_25 | AC | 1,172 ms
39,236 KB |
testcase_26 | AC | 1,184 ms
39,120 KB |
testcase_27 | AC | 1,241 ms
39,124 KB |
testcase_28 | AC | 1,293 ms
39,172 KB |
testcase_29 | AC | 1,269 ms
39,272 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define REP(i, n) FOR(i,0,n) template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } #ifdef HITONANODE_LOCAL #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl #else #define dbg(x) #endif // Nonrecursive Segment Tree (point-update, range-get) template <typename TDATA> struct NonrecursiveSegmentTree { int N; TDATA defaultRET; virtual TDATA merge(const TDATA &, const TDATA &) = 0; std::vector<TDATA> data; inline TDATA& at(int i) { return data[i]; } inline void _merge(int i) { at(i) = merge(at(i << 1), at((i << 1) + 1)); } void initialize(const std::vector<TDATA> &seq, TDATA RET_ZERO) { N = seq.size(); defaultRET = RET_ZERO; data = seq; data.insert(data.end(), seq.begin(), seq.end()); for (int i = N - 1; i; i--) _merge(i); } NonrecursiveSegmentTree() = default; void update(int pos, const TDATA &x) { assert(pos >= 0 and pos < N); at(pos + N) = x; for (int i = pos + N; i > 1;) i >>= 1, _merge(i); } // [l, r), 0-indexed TDATA get(int l, int r) { assert(l >= 0 and r <= N); TDATA retl = defaultRET, retr = defaultRET; l += N, r += N; while (l < r) { if (l & 1) retl = merge(retl, data[l++]); if (r & 1) retr = merge(data[--r], retr); l >>= 1, r >>= 1; } return merge(retl, retr); } }; #include <boost/multiprecision/cpp_dec_float.hpp> using Float = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<30>>; struct T { int deg_out; Float dx, dy; }; vector<Float> cosines, sines; const Float to_rad = acos(Float(-1.0)) / 180; struct SegmentTree : public NonrecursiveSegmentTree<T> { using SegTree = NonrecursiveSegmentTree<T>; T merge(const T &vl, const T &vr) override { int d = vl.deg_out; Float dx = vl.dx + cosines[d] * vr.dx - sines[d] * vr.dy; Float dy = vl.dy + sines[d] * vr.dx + cosines[d] * vr.dy; return T{(vl.deg_out + vr.deg_out) % 360, dx, dy}; }; SegmentTree(const std::vector<T> &seq, T defaultmin) : SegTree::NonrecursiveSegmentTree() { SegTree::initialize(seq, defaultmin); }; }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(9); cosines.resize(360), sines.resize(360); REP(d, 360) { cosines[d] = cos(Float(d) * to_rad); sines[d] = sin(Float(d) * to_rad); } int N, Q; cin >> N >> Q; vector<T> vec(N + 1); FOR(i, 1, N + 1) vec[i].dx = 1; SegmentTree tree(vec, vec[0]); while (Q--) { int q, i, x; cin >> q >> i; if (q == 0) { cin >> x; i--; vec[i].deg_out = x; tree.update(i, vec[i]); } if (q == 1) { cin >> x; vec[i].dx = x; tree.update(i, vec[i]); } if (q == 2) { auto ret = tree.get(0, i + 1); cout << ret.dx << ' ' << ret.dy << '\n'; } } }