結果

問題 No.619 CardShuffle
ユーザー 0x19f0x19f
提出日時 2018-01-25 00:12:48
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,424 bytes
コンパイル時間 2,015 ms
コンパイル使用メモリ 170,108 KB
実行使用メモリ 239,204 KB
最終ジャッジ日時 2024-06-07 22:19:13
合計ジャッジ時間 11,249 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 WA -
testcase_02 AC 1 ms
6,944 KB
testcase_03 WA -
testcase_04 AC 2 ms
6,944 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 2 ms
6,940 KB
testcase_08 WA -
testcase_09 AC 2 ms
6,940 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2 ms
6,940 KB
testcase_13 WA -
testcase_14 AC 2 ms
6,940 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 390 ms
141,852 KB
testcase_18 WA -
testcase_19 AC 414 ms
141,768 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 322 ms
151,464 KB
testcase_23 WA -
testcase_24 AC 318 ms
151,240 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 437 ms
132,440 KB
testcase_28 WA -
testcase_29 AC 499 ms
132,516 KB
testcase_30 WA -
testcase_31 AC 2 ms
6,944 KB
testcase_32 WA -
testcase_33 AC 434 ms
170,088 KB
testcase_34 WA -
testcase_35 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:24:7: warning: ‘y’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |     a += n - 1;
      |     ~~^~~~~~~~
main.cpp:79:13: note: ‘y’ was declared here
   79 |       ll x, y;
      |             ^
main.cpp:90:40: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |       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++)
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])));
  }

  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