結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー 왕지후
提出日時 2026-04-18 00:58:53
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 2,189 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 444 ms
コンパイル使用メモリ 35,840 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2026-04-18 00:59:10
合計ジャッジ時間 14,738 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>

#define MAXQ 800005

typedef struct {
    int prev;
    char mode; // 0 = LEFT, 1 = RIGHT
} Node;

Node nodes[MAXQ];
int nodeCnt = 0;

/*
stateValid[i] = 현재 문자열 길이가 i일 때, 그 prefix가 파싱 가능한지
stateTop[i]   = 그때 열린 괄호 스택의 top node index
*/
char stateValid[MAXQ];
int stateTop[MAXQ];

int main(void) {
    int Q;
    scanf("%d", &Q);

    int len = 0;
    stateValid[0] = 1;
    stateTop[0] = 0;

    for (int qi = 0; qi < Q; qi++) {
        int type;
        scanf("%d", &type);

        if (type == 1) {
            char c;
            scanf(" %c", &c);

            char valid = stateValid[len];
            int top = stateTop[len];

            len++;

            if (!valid) {
                stateValid[len] = 0;
                stateTop[len] = top;
            } else {
                if (c == '(') {
                    ++nodeCnt;
                    nodes[nodeCnt].prev = top;
                    nodes[nodeCnt].mode = 0; // LEFT
                    stateValid[len] = 1;
                    stateTop[len] = nodeCnt;
                } else if (c == '|') {
                    if (top != 0 && nodes[top].mode == 0) {
                        ++nodeCnt;
                        nodes[nodeCnt].prev = nodes[top].prev;
                        nodes[nodeCnt].mode = 1; // RIGHT
                        stateValid[len] = 1;
                        stateTop[len] = nodeCnt;
                    } else {
                        stateValid[len] = 0;
                        stateTop[len] = top;
                    }
                } else { // c == ')'
                    if (top != 0 && nodes[top].mode == 1) {
                        stateValid[len] = 1;
                        stateTop[len] = nodes[top].prev;
                    } else {
                        stateValid[len] = 0;
                        stateTop[len] = top;
                    }
                }
            }
        } else {
            // type == 2
            len--;
        }

        if (stateValid[len] && stateTop[len] == 0) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }

    return 0;
}
0