結果

問題 No.1226 I hate Robot Arms
ユーザー 👑 emthrmemthrm
提出日時 2020-09-11 23:30:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,582 bytes
コンパイル時間 2,748 ms
コンパイル使用メモリ 215,276 KB
実行使用メモリ 8,768 KB
最終ジャッジ日時 2023-08-30 10:36:36
合計ジャッジ時間 6,521 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
8,620 KB
testcase_01 WA -
testcase_02 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

struct SqrtDecomposition {
  int b, b_n;
  std::vector<int> left, right;
  std::vector<bool> need_to_be_eval;

  SqrtDecomposition(int n) : b(std::sqrt(n)) {
    b_n = (n + b - 1) / b;
    left.resize(b_n);
    right.resize(b_n);
    need_to_be_eval.assign(b_n, false);
    for (int i = 0; i < b_n; ++i) {
      left[i] = b * i;
      right[i] = i + 1 == b_n ? n : b * (i + 1);
    }
  }

  template <typename T>
  void partial_update(int idx, T val);

  template <typename T>
  void total_update(int idx, T val);

  template <typename T>
  void update(int l, int r, T val) {
    if (r <= l) return;
    int l_b = l / b, r_b = (r - 1) / b;
    if (l_b == r_b) {
      for (int i = l; i < r; ++i) partial_update(i, val);
    } else {
      for (int i = l; i < right[l_b]; ++i) partial_update(i, val);
      for (int i = l_b + 1; i < r_b; ++i) total_update(i, val);
      for (int i = left[r_b]; i < r; ++i) partial_update(i, val);
    }
  }

  void partial_query(int idx, pair<double, double> &val);

  void total_query(int idx, pair<double, double> &val);

  pair<double, double> query(int l, int r, pair<double, double> UNITY) {
    int l_b = l / b, r_b = (r - 1) / b;
    pair<double, double> res = UNITY;
    if (l_b == r_b) {
      for (int i = l; i < r; ++i) partial_query(i, res);
    } else if (l < r) {
      for (int i = l; i < right[l_b]; ++i) partial_query(i, res);
      for (int i = l_b + 1; i < r_b; ++i) total_query(i, res);
      for (int i = left[r_b]; i < r; ++i) partial_query(i, res);
    }
    return res;
  }
};

vector<int> len, deg;
vector<double> sum_x, sum_y;
vector<int> lazy;
vector<array<ll, 360>> theta;

template <typename T>
void SqrtDecomposition::partial_update(int idx, T val) {
  int tmp = idx / b;
  if (need_to_be_eval[tmp]) {
    if (lazy[tmp] > 0) {
      FOR(i, left[tmp], right[tmp]) {
        theta[tmp][deg[i]] -= len[i];
        (deg[i] += lazy[tmp]) %= 360;
        theta[tmp][deg[i]] += len[i];
      }
      lazy[tmp] = 0;
    }
    need_to_be_eval[idx] = false;
  }
  sum_x[tmp] -= len[idx] * cos(deg[idx] * M_PI / 180);
  sum_y[tmp] -= len[idx] * sin(deg[idx] * M_PI / 180);
  theta[tmp][deg[idx]] -= len[idx];
  (deg[idx] += val) %= 360;
  sum_x[tmp] += len[idx] * cos(deg[idx] * M_PI / 180);
  sum_y[tmp] += len[idx] * sin(deg[idx] * M_PI / 180);
  theta[tmp][deg[idx]] += len[idx];
}

template <typename T>
void SqrtDecomposition::total_update(int idx, T val) {
  array<ll, 360> nx{};
  REP(i, 360) {
    if (theta[idx][i] > 0) {
      sum_x[idx] -= theta[idx][i] * cos(i * M_PI / 180);
      sum_y[idx] -= theta[idx][i] * sin(i * M_PI / 180);
      nx[(i + val) % 360] += theta[idx][i];
    }
  }
  theta[idx].swap(nx);
  REP(i, 360) {
    if (theta[idx][i] > 0) {
      sum_x[idx] += theta[idx][i] * cos(i * M_PI / 180);
      sum_y[idx] += theta[idx][i] * sin(i * M_PI / 180);
    }
  }
  (lazy[idx] += val) %= 360;
  need_to_be_eval[idx] = true;
}

void SqrtDecomposition::partial_query(int idx, pair<double, double> &val) {
  int tmp = idx / b;
  if (need_to_be_eval[tmp]) {
    if (lazy[tmp] > 0) {
      FOR(i, left[tmp], right[tmp]) {
        theta[tmp][deg[i]] -= len[i];
        (deg[i] += lazy[tmp]) %= 360;
        theta[tmp][deg[i]] += len[i];
      }
      lazy[tmp] = 0;
    }
    need_to_be_eval[idx] = false;
  }
  val.first += len[idx] * cos(deg[idx] * M_PI / 180);
  val.second += len[idx] * sin(deg[idx] * M_PI / 180);
}

void SqrtDecomposition::total_query(int idx, pair<double, double> &val) {
  val.first += sum_x[idx];
  val.second += sum_y[idx];
}

int main() {
  int n, q; cin >> n >> q;
  SqrtDecomposition sd(n);
  len.assign(n, 1);
  deg.assign(n, 0);
  sum_x.resize(sd.b_n);
  sum_y.assign(sd.b_n, 0);
  lazy.assign(sd.b_n, 0);
  theta.resize(sd.b_n);
  REP(i, sd.b_n) {
    sum_x[i] = sd.right[i] - sd.left[i];
    theta[i][0] = sd.right[i] - sd.left[i];
  }
  while (q--) {
    int query; cin >> query;
    if (query == 0) {
      int i, x; cin >> i >> x; --i;
      sd.update(i, n, (x - deg[i] + 360) % 360);
    } else if (query == 1) {
      int i, x; cin >> i >> x; --i;
      int tmp = i / sd.b;
      sd.partial_update(i, 0);
      sum_x[tmp] -= len[i] * cos(deg[i] * M_PI / 180);
      sum_y[tmp] -= len[i] * sin(deg[i] * M_PI / 180);
      theta[tmp][deg[i]] -= len[i];
      len[i] = x;
      sum_x[tmp] += len[i] * cos(deg[i] * M_PI / 180);
      sum_y[tmp] += len[i] * sin(deg[i] * M_PI / 180);
      theta[tmp][deg[i]] += len[i];
    } else if (query == 2) {
      int i; cin >> i; --i;
      auto [ans_x, ans_y] = sd.query(0, i + 1, {0, 0});
      cout << ans_x << ' ' << ans_y << '\n';
    }
    // REP(i, sd.b_n) cout << '(' << sum_x[i] << ',' << sum_y[i] << ')' << " \n"[i + 1 == sd.b_n];
  }
  return 0;
}
0