結果

問題 No.619 CardShuffle
ユーザー 0x19f0x19f
提出日時 2018-01-25 00:45:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 854 ms / 3,000 ms
コード長 2,795 bytes
コンパイル時間 1,465 ms
コンパイル使用メモリ 159,460 KB
実行使用メモリ 354,804 KB
最終ジャッジ日時 2023-08-27 02:34:23
合計ジャッジ時間 14,740 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,384 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 600 ms
250,708 KB
testcase_17 AC 531 ms
209,052 KB
testcase_18 AC 603 ms
251,300 KB
testcase_19 AC 529 ms
208,684 KB
testcase_20 AC 668 ms
293,308 KB
testcase_21 AC 487 ms
227,268 KB
testcase_22 AC 458 ms
223,188 KB
testcase_23 AC 450 ms
227,280 KB
testcase_24 AC 446 ms
222,892 KB
testcase_25 AC 428 ms
231,444 KB
testcase_26 AC 677 ms
274,700 KB
testcase_27 AC 562 ms
194,700 KB
testcase_28 AC 705 ms
274,168 KB
testcase_29 AC 560 ms
194,816 KB
testcase_30 AC 854 ms
354,804 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 684 ms
292,848 KB
testcase_33 AC 573 ms
251,068 KB
testcase_34 AC 623 ms
276,640 KB
testcase_35 AC 244 ms
67,616 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:25:5: warning: ‘y’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     a += n - 1;
     ^
main.cpp:87:13: note: ‘y’ was declared here
       ll x, y;
             ^
main.cpp:25:5: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     a += n - 1;
     ^
main.cpp:87:10: note: ‘x’ was declared here
       ll x, y;
          ^

ソースコード

diff #

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define MOD 1000000007LL
using namespace std;
typedef long long ll;

/* 0-indexed, [0, n) */
template<typename T> class SegmentTree {
  vector<T> vec;
  ll n;          // size of vector
  T e;           // unity of monoid
  T (*op)(T, T); // binary operator of monoid

public:
  SegmentTree(ll _n, T _e, T (*_op)(T, T)) : e(_e), op(_op), n(1) {
    while(n < _n) n *= 2;
    vec.resize(n * 2 - 1, e);
  }

  T query(ll a, ll b) { // query for [a, b)
    return rquery(a, b, 0, 0, n);
  }

  void update(ll a, T k) { // update for a-th value
    a += n - 1;
    vec[a] = k;
    while(a > 0) {
      a = (a - 1) / 2;
      vec[a] = op(vec[a * 2 + 1], vec[a * 2 + 2]);
    }
  }

private:
  T rquery(ll a, ll b, ll k, ll l, ll r) {
    if(r <= a || b <= l) return e;
    if(a <= l && r <= b) return vec[k];
    T vl = rquery(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = rquery(a, b, k * 2 + 2, (l + r) / 2, r);
    return op(vl, vr);
  }
};

struct node {
  ll type;
  ll x, y, z;

  node(ll x): type(1), x(x) {}
  node(ll x, ll y, ll z): type(0), x(x), y(y), z(z) {}
  node(char op, ll v) {
    if(op == '+') { type = 0; x = 1; y = 0; z = v; }
    if(op == '*') { type = 1; x = v; }
  }

  ll value() {
    if(type == 1) return x;
    return (y + z) % MOD;
  };
};

node op(node p, node q) {
  if(p.type == 1 && q.type == 1) return *(new node(p.x * q.x % MOD));
  if(p.type == 1 && q.type == 0) return *(new node(p.x * q.x % MOD, q.y, q.z));
  if(p.type == 0 && q.type == 1) return *(new node(p.x, p.y, p.z * q.x % MOD));
  return *(new node(p.x, (((p.y + ((p.z * q.x) % MOD)) % MOD) + q.y) % MOD, q.z));
}

int main(void) {
  ll N;
  cin >> N;
  vector<char> OP(N);
  vector<ll> V(N);
  SegmentTree<node> segtree(N, *(new node(1)), op);
  REP(i, 0, (N + 1) / 2) {
    ll v;
    if(i == 0) OP[i] = '+'; else cin >> OP[i];
    cin >> V[i];
    segtree.update(i, *(new node(OP[i], V[i])));
  }

  ll Q;
  cin >> Q;
  vector<char> T(Q);
  vector<ll> X(Q), Y(Q);
  REP(i, 0, Q) cin >> T[i] >> X[i] >> Y[i], X[i]--, Y[i]--;
  REP(i, 0, Q) {
    if(T[i] == '!') {
      ll x, y;
      if(X[i] % 2 == 0 && Y[i] % 2 == 0) {
        x = X[i] / 2;
        y = Y[i] / 2;
        swap(V[x], V[y]);
      }
      if(X[i] % 2 == 1 && Y[i] % 2 == 1) {
        x = X[i] / 2 + 1;
        y = Y[i] / 2 + 1;
        swap(OP[x], OP[y]);
      }
      segtree.update(x, *(new node(OP[x], V[x])));
      segtree.update(y, *(new node(OP[y], V[y])));
    }
    if(T[i] == '?') {
      ll x = X[i] / 2, y = Y[i] / 2 + 1;
      if(OP[x] == '*') segtree.update(x, *(new node('+', V[x])));
      node r = segtree.query(x, y);
      cout << r.value() << endl;
      if(OP[x] == '*') segtree.update(x, *(new node(OP[x], V[x])));
    }
  }
}
0