結果

問題 No.1226 I hate Robot Arms
ユーザー Ricky_ponRicky_pon
提出日時 2020-09-11 23:46:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,712 bytes
コンパイル時間 2,272 ms
コンパイル使用メモリ 215,976 KB
実行使用メモリ 13,884 KB
最終ジャッジ日時 2024-06-10 10:56:26
合計ジャッジ時間 6,577 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 OLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:174:27: warning: narrowing conversion of 'i' from 'int' to 'double' [-Wnarrowing]
  174 |     rep(i, n + 1) v[i] = {i, 0, 1};
      |                           ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define For(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); ++(i))
#define rFor(i, a, b) for (int(i) = (int)(a)-1; (i) >= (int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T div_floor(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

template <class T, class E>
struct LazySegTree {
    using F = function<T(T, T)>;
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;
    using P = function<E(E, int)>;
    int sz = 1, seq_sz;
    F f;
    G g;
    H h;
    T et;
    E ee;
    P p;
    int cur = 0;
    vector<T> node;
    vector<E> lazy;
    vector<int> idx, len;

    LazySegTree(
        int sz_, T et_, E ee_, F f_, G g_, H h_,
        P p_ = [](E a, int b) { return a; })
        : seq_sz(sz_), et(et_), ee(ee_), f(f_), g(g_), h(h_), p(p_) {
        while (sz < sz_) sz <<= 1;
        node.resize(sz << 1, et);
        lazy.resize(sz << 1, ee);
        idx.resize(sz, -1);
        len.resize(sz << 1, 0);
        For(i, sz, sz << 1) len[i] = 1;
        rFor(i, sz, 1) len[i] = len[i << 1] + len[(i << 1) + 1];
    }

    void build(vector<T> &a) {
        rep(i, a.size()) node[i + sz] = a[i];
        rFor(i, sz, 1) node[i] = f(node[i << 1], node[(i << 1) + 1]);
    }

    void build(T x) {
        rep(i, seq_sz) node[i + sz] = x;
        rFor(i, sz, 1) node[i] = f(node[i << 1], node[(i << 1) + 1]);
    }

    inline void push(int i) {
        if (lazy[i] == ee) return;
        if (i < sz) {
            lazy[i << 1] = h(lazy[i << 1], lazy[i]);
            node[i << 1] = g(node[i << 1], p(lazy[i], len[i << 1]));
            lazy[(i << 1) + 1] = h(lazy[(i << 1) + 1], lazy[i]);
            node[(i << 1) + 1] =
                g(node[(i << 1) + 1], p(lazy[i], len[(i << 1) + 1]));
        }
        lazy[i] = ee;
    }

    inline void prop(int l, int r) {
        cur = 0;
        if (l == sz && r == sz << 1) return;
        l = (l / (l & -l)) >> 1;
        r = (r / (r & -r)) >> 1;
        while (l > 1 || r > 1) {
            if (l >= r) {
                idx[cur++] = l;
                l >>= 1;
            } else {
                idx[cur++] = r;
                r >>= 1;
            }
        }
        idx[cur++] = 1;

        rrep(k, cur) push(idx[k]);
    }

    void update(int l, int r, E x) {
        l += sz;
        r += sz;
        prop(l, r);
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                lazy[l] = h(lazy[l], x);
                node[l] = g(node[l], p(x, len[l]));
                ++l;
            }
            if (r & 1) {
                --r;
                lazy[r] = h(lazy[r], x);
                node[r] = g(node[r], p(x, len[r]));
            }
        }
        rep(k, cur) {
            int i = idx[k];
            if (i < sz) node[i] = f(node[i << 1], node[(i << 1) + 1]);
        }
    }

    T query(int l, int r) {
        l += sz;
        r += sz;
        prop(l, r);
        T vl = et, vr = et;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vl = f(vl, node[l++]);
            if (r & 1) vr = f(node[--r], vr);
        }
        return f(vl, vr);
    }
};

using mat = array<array<double, 3>, 3>;

mat mul(mat a, mat b) {
    mat c;
    rep(i, 3) rep(j, 3) {
        c[i][j] = 0;
        rep(k, 3) c[i][j] += a[i][k] * b[k][j];
    }
    return c;
}

array<double, 3> mul(mat a, array<double, 3> v) {
    array<double, 3> vv = {0, 0, 0};
    rep(i, 3) rep(j, 3) vv[i] += a[i][j] * v[j];
    return vv;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    array<double, 3> v[n + 1];
    int len[n];
    rep(i, n) len[i] = 1;
    rep(i, n + 1) v[i] = {i, 0, 1};
    auto f = [&](mat a, mat b) { return mul(a, b); };
    mat e;
    rep(i, 3) {
        rep(j, 3) e[i][j] = 0;
        e[i][i] = 1;
    }
    LazySegTree<mat, mat> lst(n + 1, e, e, f, f, f);

    rep(_, q) {
        int t;
        scanf("%d", &t);
        if (t == 0) {
            int pos, x;
            scanf("%d%d", &pos, &x);
            --pos;
            auto p = mul(lst.query(pos, pos + 1), v[pos]);
            auto q = mul(lst.query(pos + 1, pos + 2), v[pos + 1]);

            mat a;
            rep(i, 3) rep(j, 3) a[i][j] = 0;
            a[0][0] = a[1][1] =
                cos(x * M_PI / 180 - atan2(q[1] - p[1], q[0] - p[0]));
            a[0][1] = a[1][0] =
                sin(x * M_PI / 180 - atan2(q[1] - p[1], q[0] - p[0]));
            a[0][1] *= -1;
            a[2][2] = 1;
            /*rep(i, 3) {
                rep(j, 3) printf("%lf ", a[i][j]);
                printf("\n");
            }*/

            mat b;
            rep(i, 3) {
                rep(j, 3) b[i][j] = 0;
                b[i][i] = 1;
            }
            b[0][2] = -p[0];
            b[1][2] = -p[1];
            /*rep(i, 3) {
                rep(j, 3) printf("%lf ", b[i][j]);
                printf("\n");
            }*/

            lst.update(pos + 1, n + 1, b);
            lst.update(pos + 1, n + 1, a);
            b[0][2] *= -1;
            b[1][2] *= -1;
            lst.update(pos + 1, n + 1, b);
        } else if (t == 1) {
            int pos, x;
            scanf("%d%d", &pos, &x);
            --pos;
            auto p = mul(lst.query(pos, pos + 1), v[pos]);
            auto q = mul(lst.query(pos + 1, pos + 2), v[pos + 1]);

            mat b;
            rep(i, 3) {
                rep(j, 3) b[i][j] = 0;
                b[i][i] = 1;
            }
            b[0][2] = (q[0] - p[0]) * (x - len[pos]) / len[pos];
            b[1][2] = (q[1] - p[1]) * (x - len[pos]) / len[pos];
            len[pos] = x;
            lst.update(pos + 1, n + 1, b);
        } else {
            int i;
            scanf("%d", &i);
            auto a = lst.query(i, i + 1);
            auto p = mul(a, v[i]);
            printf("%.10lf %.10lf\n", p[0], p[1]);
        }
        printf("%d\n", _);
        rep(i, n + 1) {
            auto p = mul(lst.query(i, i + 1), v[i]);
            printf("(%lf %lf %lf)\n", p[0], p[1], p[2]);
        }
    }
}
0