QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#283070#1194. Parehtneses EditorNYCU_template#WA 1ms6816kbC++201.3kb2023-12-13 19:14:302023-12-13 19:14:30

Judging History

你现在查看的是最新测评结果

  • [2023-12-13 19:14:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6816kb
  • [2023-12-13 19:14:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int N = 2e5 + 5;
ll dp[N], n, match[N];
string s;
stack<pair<char, ll>> st1, st2;
int main() {
    cin >> s;
    n = (int)s.size();

    memset(match, -1, sizeof(match));

    ll inval_cnt = 0, ans = 0;
    for(int i = 0; i < n; i++) {
        char c = s[i];
        if(c == '-') {
            char cc = st2.top().first;
            int ii = st2.top().second;
            if(cc == ')' && match[ii] != -1) {
                ans -= dp[ii];
                st1.emplace('(', match[ii]);   
            } else {
                st1.pop();
            }
            st2.pop();
        } else {
            if(c == '(') st1.emplace(c, i);
            else {
                if(st1.empty() || st1.top().first == ')') {
                    st1.emplace(c, i);
                } else {
                    int l_id = st1.top().second;
                    match[i] = l_id;
                    if(l_id) dp[i] = dp[l_id - 1] + 1;
                    else dp[i] = 1;
                    ans += dp[i];
                    st1.pop();

                    // cerr << "match[" << i << "] = " << match[i] << endl;
                }
            }
            st2.emplace(c, i);
        }

        cout << ans << "\n";
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5356kb

input:

(()())---)

output:

0
0
1
1
3
4
3
1
1
2

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 6816kb

input:

()--()()----)(()()))

output:

0
1
0
0
0
1
1
3
1
1
0
0
0
0
0
1
1
3
4
4

result:

ok 20 numbers

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 6160kb

input:

))(((-)(()((---(-)(-())-(()()(-)--(())))--()((())-)(()(())((-))))(-(((()((()()()()))-(())((((--))-())-)(-(--))))((((-)(-(-)((((()--(---)(-))()(-)(()()-(())()(()()((()()))))(()(()(-(--)-()((()(((()-))-)(()-()()-(-((-)(-)(((()-)))))-())()-(()((()(-)()))((-))())))()()()(-(-(())-()(()-)-))((()))((--(-()...

output:

0
0
0
0
0
0
1
1
1
2
2
2
2
2
1
1
1
2
2
2
2
3
5
3
3
3
4
4
6
6
6
7
6
4
4
4
5
6
8
9
8
6
6
7
7
7
7
8
9
8
9
9
9
10
10
10
11
13
13
13
13
16
18
20
22
22
22
22
22
22
22
23
23
23
23
24
24
26
26
29
29
33
34
36
34
34
34
35
36
36
36
36
36
36
36
37
39
37
37
38
40
38
40
40
40
40
40
38
40
42
43
44
44
44
44
44
44
45...

result:

wrong answer 22nd numbers differ - expected: '4', found: '3'