結果

問題 No.619 CardShuffle
ユーザー 0x19f0x19f
提出日時 2018-01-25 00:45:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 760 ms / 3,000 ms
コード長 2,795 bytes
コンパイル時間 1,670 ms
コンパイル使用メモリ 168,824 KB
実行使用メモリ 354,816 KB
最終ジャッジ日時 2024-06-07 22:22:17
合計ジャッジ時間 12,695 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 530 ms
250,860 KB
testcase_17 AC 459 ms
209,072 KB
testcase_18 AC 525 ms
251,432 KB
testcase_19 AC 465 ms
208,896 KB
testcase_20 AC 573 ms
293,504 KB
testcase_21 AC 420 ms
227,456 KB
testcase_22 AC 413 ms
223,232 KB
testcase_23 AC 423 ms
227,328 KB
testcase_24 AC 410 ms
223,072 KB
testcase_25 AC 403 ms
231,460 KB
testcase_26 AC 644 ms
274,712 KB
testcase_27 AC 506 ms
194,728 KB
testcase_28 AC 630 ms
274,408 KB
testcase_29 AC 517 ms
194,852 KB
testcase_30 AC 760 ms
354,816 KB
testcase_31 AC 1 ms
5,376 KB
testcase_32 AC 574 ms
293,356 KB
testcase_33 AC 526 ms
251,108 KB
testcase_34 AC 602 ms
276,608 KB
testcase_35 AC 229 ms
67,584 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:25:7: warning: ‘y’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |     a += n - 1;
      |     ~~^~~~~~~~
main.cpp:87:13: note: ‘y’ was declared here
   87 |       ll x, y;
      |             ^
main.cpp:98:40: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |       segtree.update(x, *(new node(OP[x], V[x])));
      |                                        ^

ソースコード

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