結果
問題 | No.1226 I hate Robot Arms |
ユーザー |
|
提出日時 | 2020-09-11 22:59:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 338 ms / 2,000 ms |
コード長 | 4,124 bytes |
コンパイル時間 | 2,224 ms |
コンパイル使用メモリ | 205,784 KB |
最終ジャッジ日時 | 2025-01-14 11:23:05 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i = 0; i < n; i++)#define rep2(i, x, n) for(int i = x; i <= n; i++)#define rep3(i, x, n) for(int i = x; i >= n; i--)#define elif else if#define sp(x) fixed << setprecision(x)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;const ll MOD = 1000000007;//const ll MOD = 998244353;const int inf = (1<<30)-1;const ll INF = (1LL<<60)-1;const double pi = acos(-1.0);const double EPS = 1e-10;template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};template<typename Monoid, typename Operator_Monoid>struct Lazy_Segment_Tree{vector<Monoid> seg;vector<Operator_Monoid> lazy;const Monoid e1;const Operator_Monoid e2;const int n;Monoid f(const Monoid &a, const Monoid &b) const {return a+b;}Monoid g(const Monoid &a, const Operator_Monoid &b) const {return a*b;}Operator_Monoid h(const Operator_Monoid &a, const Operator_Monoid &b) const {return a*b;}Lazy_Segment_Tree(int N, const Monoid &e1, const Operator_Monoid &e2): e1(e1), e2(e2), n(1<<(32-__builtin_clz(N-1))){seg.assign(2*n, e1), lazy.assign(2*n, e2);}void set(int i, const Monoid &x) {seg[n+i] = x;}void build(){rep3(i, n-1, 1) seg[i] = f(seg[2*i], seg[2*i+1]);}void init(int N, const Monoid &x){rep(i, N) set(i, x);build();}void eval(int i, int l, int r){if(lazy[i] != e2){//seg[i] = g(seg[i], lazy[i]*(r-l));seg[i] = g(seg[i], lazy[i]);if(r-l > 1){lazy[2*i] = h(lazy[2*i] ,lazy[i]);lazy[2*i+1] = h(lazy[2*i+1], lazy[i]);}lazy[i] = e2;}}void add(int a, int b, const Operator_Monoid &x, int i, int l, int r){eval(i, l, r);if(a >= r || b <= l) return;if(a <= l && r <= b){lazy[i] = h(lazy[i], x);eval(i, l, r);}else{add(a, b, x, 2*i, l, (l+r)/2);add(a, b, x, 2*i+1, (l+r)/2, r);seg[i] = f(seg[2*i], seg[2*i+1]);}}void add(int a, int b, const Operator_Monoid &x) {add(a, b, x, 1, 0, n);}Monoid query(int a, int b, int i, int l, int r){eval(i, l, r);if(a >= r || b <= l) return e1;if(a <= l && r <= b) return seg[i];Monoid vl = query(a, b, 2*i, l, (l+r)/2);Monoid vr = query(a, b, 2*i+1, (l+r)/2, r);return f(vl, vr);}Monoid query(int a, int b) {return query(a, b, 1, 0, n);}void update(int i, int l, int r){seg[i] = g(seg[i], lazy[i]);if(r-l > 1){lazy[2*i] = h(lazy[2*i], lazy[i]);lazy[2*i+1] = h(lazy[2*i+1], lazy[i]);update(2*i, l, (l+r)/2);update(2*i+1, (l+r)/2, r);}lazy[i] = e2;}void update() {update(1, 0, n);}Monoid operator [] (int i) const {return seg[n+i];}void clear(){fill(all(seg), e1), fill(all(lazy), e2);}};int main(){int N, Q;cin >> N >> Q;Lazy_Segment_Tree<complex<double>, complex<double>> seg(N, {0.0, 0.0}, {1.0, 0.0});seg.init(N, {1.0, 0.0});double t[N], d[N];fill(t, t+N, 0.0), fill(d, d+N, 1.0);while(Q--){int q, i; cin >> q >> i;if(q == 2){complex<double> ans = seg.query(0, i);cout << sp(10) << real(ans) << ' ' << imag(ans) << endl;}else{double x; cin >> x;if(q == 0){seg.add(i-1, N, polar(1.0, (x-t[i-1])*pi/180.0));t[i-1] = x;}else{seg.add(i-1, i, {x/d[i-1], 0.0});d[i-1] = x;}}}}