結果
問題 | No.1226 I hate Robot Arms |
ユーザー |
|
提出日時 | 2020-09-11 22:30:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 524 ms / 2,000 ms |
コード長 | 5,441 bytes |
コンパイル時間 | 1,838 ms |
コンパイル使用メモリ | 171,064 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2025-01-01 21:20:46 |
合計ジャッジ時間 | 15,410 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define SZ(x) (int)(x.size())#define REP(i, n) for(int i=0;i<(n);++i)#define FOR(i, a, b) for(int i=(a);i<(b);++i)#define RREP(i, n) for(int i=(int)(n);i>=0;--i)#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)#define ALL(a) (a).begin(),(a).end()#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;using ll = long long;using vi = vector<int>;using vvi = vector<vi>;using vll = vector<ll>;using vvll = vector<vll>;using P = pair<int, int>;const double eps = 1e-8;const ll MOD = 1000000007;const int INF = INT_MAX / 2;const ll LINF = LLONG_MAX / 2;template <typename T1, typename T2>bool chmax(T1 &a, const T2 &b) {if(a < b) {a = b; return true;}return false;}template <typename T1, typename T2>bool chmin(T1 &a, const T2 &b) {if(a > b) {a = b; return true;}return false;}template<typename T1, typename T2>ostream& operator<<(ostream &os, const pair<T1, T2> p) {os << p.first << ":" << p.second;return os;}template<class T>ostream &operator<<(ostream &os, const vector<T> &v) {REP(i, SZ(v)) {if(i) os << " ";os << v[i];}return os;}template<typename M>struct SegmentTree {/*** @brief コンストラクタ. O(n)* @param[in] n セグ木のサイズ.* @param[in] f モノイドの演算(query).* @param[in] g モノイドの演算(update).* @param[in] e モノイドの単位元.* @details 使い方* e.g. Update and Range Minimum* SegmentTree<int> segt(* n,* [](int a,int b){ return min(a+b); },* [](int a, int b){ return b; },* INF);* // 全て単位元で初期化される.*/SegmentTree(int n,const function<M(M,M)>& f,const function<M(M, M)>& g,const M& e) : n(n), f(f), g(g), e(e) {sz = 1;while (sz < n) sz <<= 1;data.assign(2 * sz, e);}/*** @brief 全体に初期値を入れる. O(n)* @param[in] v 要素モノイドのvector. 初期化する.* @details 使い方* segt.build(vector<int>(n, 0));*/void build(const vector<M>& v) {assert(v.size() <= n);for (int i = 0; i < v.size(); ++i) {data[i + sz] = v[i];}for (int i = sz-1; i > 0; --i) {data[i] = f(data[2 * i], data[2 * i + 1]);}}/*** @brief 指定した位置に更新クエリを実行する O(log n)* @param[in] idx 位置idxに作用させる* @param[in] val 値xをg(data[idx+sz], val)で更新する*/void update(int idx, M val) {idx += sz;data[idx] = g(data[idx], val);while(idx >>= 1) {data[idx] = f(data[2*idx], data[2*idx+1]);}}/*** @brief 指定した区間に取得クエリを実行する. O(log n)* @param[in] l, r 区間[l, r) を取得する.* @return 取得した値.* @details 使い方* e.g. Range Minimum* int l, r; // 区間[l, r) のminを取得したい.* cout << segt.query(l, r) << endl;*/M query(int a, int b) const {return query(a, b, 1, 0, sz);}/*** @brief 指定したindexの要素を取得. O(1)* @param[in] i 取得したい要素のindex* @return 取得した値.*/M operator[](int k) const {return data[k + sz];}/*** @brief vector みたいに出力.*/friend ostream& operator<<(ostream& os, SegmentTree& s) {os << "[";for (int i = 0; i < s.n; ++i) {if (i) os << " ";os << s[i];}return os << "]";}private:int n, sz;vector<M> data;const function<M(M,M)> f, g;const M e;M query(int a, int b, int k, int l, int r) const {if (r <= a || b <= l) {return e;} else if (a <= l && r <= b) {return data[k];} else {return f(query(a,b,2*k, l,(l+r)/2),query(a,b,2*k+1,(l+r)/2,r));}}};struct M {double len;double theta;double theta2;M() {len = 1.0;theta = 0.0;theta2 = 0.0;}M(double len, double theta, double theta2): len(len), theta(theta), theta2(theta2) {}};M operator+ (M m1, M m2) {complex<double> c(m1.len * cos(m1.theta) + m2.len * cos(m1.theta + m1.theta2 + m2.theta), m1.len * sin(m1.theta) + m2.len * sin(m1.theta + m1.theta2 + m2.theta));return {abs(c), arg(c), m1.theta + m1.theta2 + m2.theta + m2.theta2 - arg(c)};}int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(10);int n, q; cin >> n >> q;SegmentTree<M> st(n,[](M a, M b){return a + b;},[](M a, M b){return b;},M(0, 0, 0));vector<M> v(n, M(1, 0, 0));st.build(v);REP(_, q) {int t; cin >> t;if(t == 0) {int i; double x; cin >> i >> x;x = x * acos(-1) / 180.0;i--;M now = st.query(i, i+1);now.theta = x;st.update(i, now);} else if(t == 1) {int i; double x; cin >> i >> x;i--;M now = st.query(i, i+1);now.len = x;st.update(i, now);} else if(t == 2) {int i; cin >> i;i--;M now = st.query(0, i+1);cout << now.len * cos(now.theta) << " " << now.len * sin(now.theta) << endl;}/*REP(i, n) {M now = st.query(i, i+1);cout << now.len << " " << now.theta << " " << now.theta2 << endl;}cout << endl;*/}return 0;}