結果

問題 No.457 (^^*)
コンテスト
ユーザー flippergo
提出日時 2025-01-02 16:38:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,945 bytes
コンパイル時間 1,179 ms
コンパイル使用メモリ 88,476 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-02 16:38:35
合計ジャッジ時間 6,905 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    string S;
    cin >> S;
    
    int N = S.length();
    S = "0" + S;  // Pythonのような文字列結合
    vector<int> A(N + 1, 0);
    vector<int> B(N + 1, 0);
    
    for (int i = 1; i <= N; i++) {
        if (S[i] == '^') {
            A[i] = A[i - 1] + 1;
            B[i] = B[i - 1];
        } else if (S[i] == '*') {
            A[i] = A[i - 1];
            B[i] = B[i - 1] + 1;
        } else {
            A[i] = A[i - 1];
            B[i] = B[i - 1];
        }
    }
    
    int ans1 = 0, ans2 = 0;

    for (int i = 1; i <= N - 4; i++) {
        if (S[i] == '(') {
            for (int j = i + 4; j <= N; j++) {
                if (S[j] == ')') {
                    // 最初の二分探索
                    int high = j;
                    int low = i;
                    while (high - low > 1) {
                        int mid = (high + low) / 2;
                        if (A[mid] - A[i] >= 2) {
                            high = mid;
                        } else {
                            low = mid;
                        }
                    }
                    if (A[high] - A[i] >= 2 && B[j] - B[high] >= 1) {
                        ans1++;
                    }

                    // 2回目の二分探索
                    high = j;
                    low = i;
                    while (high - low > 1) {
                        int mid = (high + low) / 2;
                        if (A[j] - A[mid] >= 2) {
                            low = mid;
                        } else {
                            high = mid;
                        }
                    }
                    if (A[j] - A[low] >= 2 && B[low] - B[i] >= 1) {
                        ans2++;
                    }
                }
            }
        }
    }

    cout << ans1 << " " << ans2 << endl;

    return 0;
}
0