結果

問題 No.1863 Xor Sum 2...?
ユーザー srjywrdnprkt
提出日時 2025-03-30 15:16:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 2,101 bytes
コンパイル時間 3,529 ms
コンパイル使用メモリ 277,872 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-30 15:17:04
合計ジャッジ時間 6,351 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       f(l, r) = A_l+...+A_r - (A_l xor ... xor A_r)は単調増加
       (繰り上がりが発生すると増加し、発生しなければそのまま)
       B_l xor ... xor B_r = 0
       となる場合について、尺取り法でlに対して
       f(l, r) = 0となる最大のrを探す。
       B_l xor ... xor B_i = 0となるようなl<=i<=rの数を答えに加算。
       これは、
       C_i = B_1 xor ... xor B_i
       D_i = (C_k = 0)となるようなk<=iの数としておくと、
       C_(l-1) = 0のとき、D_r-D_(l-1) (0の数)
       C_(l-1) = 1のとき、(r-l+1)-(D_r-D_(l-1)) (1の数)

       f(l, r2) <= 1となる最大のr2を探す。
       B_l xor ... xor B_i = 1となるようなr+1<=i<=r2の数を答えに加算。
       C_r = 0のとき、(r2-r)-(D_r2-D_r) (1の数)
       C_r = 1のとき、D_r2-D_r (0の数)
    */

    ll N;
    cin >> N;
    vector<ll> A(N+1), B(N+1), C(N+1), D(N+1);
    for (int i=1; i<=N; i++) cin >> A[i];
    for (int i=1; i<=N; i++){
        cin >> B[i];
        C[i] = C[i-1] ^ B[i];
        if (C[i] == 0) D[i]++;
        D[i] += D[i-1];
    }
    ll x0=0, y0=0, x1=0, y1=0, r0=1, r1=1, ans=0;
    for (int l=1; l<=N; l++){
        while(r0<=N && y0+A[r0]-(x0^A[r0]) == 0){
            y0 += A[r0];
            x0 ^= A[r0];
            r0++;
        }
        while(r1<=N && y1+A[r1]-(x1^A[r1]) <= 1){
            y1 += A[r1];
            x1 ^= A[r1];
            r1++;
        }
        r0--; r1--;
        if (C[l-1] == 0) ans += D[r0] - D[l-1];
        else ans += (r0-l+1) - (D[r0] - D[l-1]);
        if (r1 != r0){
            if (C[r0] == 1) ans += D[r1] - D[r0];
            else ans += (r1-r0) - (D[r1] - D[r0]);
        }
        r0++; r1++;
        y0 -= A[l];
        x0 ^= A[l];
        y1 -= A[l];
        x1 ^= A[l];
    } 

    cout << ans << endl;

    return 0;
}
0