結果

問題 No.619 CardShuffle
ユーザー 0x19f
提出日時 2018-01-25 00:45:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 895 ms / 3,000 ms
コード長 2,795 bytes
コンパイル時間 1,998 ms
コンパイル使用メモリ 168,304 KB
実行使用メモリ 354,688 KB
最終ジャッジ日時 2024-12-26 08:31:02
合計ジャッジ時間 15,085 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
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