結果

問題 No.619 CardShuffle
ユーザー 0x19f0x19f
提出日時 2018-01-25 00:11:39
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,486 bytes
コンパイル時間 2,400 ms
コンパイル使用メモリ 159,380 KB
実行使用メモリ 238,856 KB
最終ジャッジ日時 2023-08-27 02:31:32
合計ジャッジ時間 17,948 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:24:5: warning: ‘y’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     a += n - 1;
     ^
main.cpp:81:13: note: ‘y’ was declared here
       ll x, y;
             ^
main.cpp:24:5: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     a += n - 1;
     ^
main.cpp:81: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++)
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 x, y, z;

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

  ll value() { return y + z; };
};

node op(node p, node q) {
  return *(new node(p.x, p.y + p.z * q.x + q.y, q.z));
}

int main(void) {
  ll N;
  cin >> N;
  vector<char> OP(N);
  vector<ll> V(N);
  SegmentTree<node> segtree(N, *(new node()), 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])));
  }

  REP(i, 0, N) cout << "  " << OP[i] << " " << V[i] << endl;

  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])));
      cout << segtree.query(x, y).value() << endl;
      if(OP[x] == '*') segtree.update(x, *(new node(OP[x], V[x])));
    }
  }
}
0