結果

問題 No.2080 Simple Nim Query
ユーザー AngrySadEightAngrySadEight
提出日時 2022-09-03 13:35:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 405 ms / 3,000 ms
コード長 2,274 bytes
コンパイル時間 645 ms
コンパイル使用メモリ 76,992 KB
実行使用メモリ 5,552 KB
最終ジャッジ日時 2023-09-03 02:47:21
合計ジャッジ時間 4,449 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 258 ms
4,380 KB
testcase_04 AC 264 ms
4,376 KB
testcase_05 AC 378 ms
5,420 KB
testcase_06 AC 405 ms
5,540 KB
testcase_07 AC 394 ms
5,552 KB
testcase_08 AC 344 ms
5,396 KB
testcase_09 AC 347 ms
5,436 KB
testcase_10 AC 372 ms
5,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

struct BIT{
    int N;
    vector<ll> vec;
    BIT(int N_): N(N_), vec(N + 1){
        for (int i = 0; i < N + 1; i++){
            vec[i] = 0;
        }
    }
    
    void add(int p, ll x){
        for (int i = p; i <= N; i += (i & -i)){
            vec[i] += x;
        }
    }

    ll sum(int p){
        ll sum = 0;
        for (int i = p; i > 0; i -= (i & -i)){
            sum += vec[i];
        }
        return sum;
    }
};

int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    BIT bit(N);
    for (int i = 0; i < N; i++){
        if (A[i] == 1) bit.add(i + 1, 1);
    }
    for (int i = 0; i < Q; i++){
        int T;
        cin >> T;
        if (T == 1){
            int X, Y;
            cin >> X >> Y;
            if (A[X - 1] == 1 && Y != 1){
                bit.add(X, -1);
            }
            else if (A[X - 1] != 1 && Y == 1){
                bit.add(X, 1);
            }
            A[X - 1] = Y;
        }
        else{
            int X, Y;
            cin >> X >> Y;
            ll sumY = bit.sum(Y);
            ll sumX = bit.sum(X - 1);
            if (Y - X + 1 == sumY - sumX){
                if ((sumY - sumX) % 2 == 0){
                    cout << "S" << endl;
                }
                else{
                    cout << "F" << endl;
                }
            }
            else if (A[Y - 1] != 1){
                cout << "F" << endl;
            }
            else{
                //どこまで1であるかを二分探索
                int left = X - 1;
                int right = Y;
                while(right - left > 1){
                    int center = (left + right) / 2;
                    ll sumC = bit.sum(center);
                    if (Y - center == sumY - sumC){
                        right = center;
                    }
                    else{
                        left = center;
                    }
                }
                if ((Y - right) % 2 == 0){
                    cout << "F" << endl;
                }
                else{
                    cout << "S" << endl;
                }
            }
        }
    }
}
0