QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#260239#1194. Parehtneses Editorlemonilemon#WA 2ms3584kbC++202.1kb2023-11-21 22:48:052023-11-21 22:48:05

Judging History

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

  • [2023-11-21 22:48:05]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3584kb
  • [2023-11-21 22:48:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef genshin
#include <experimental/iterator>
#endif
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using uint = unsigned int;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 46 * ll(1e17);
const int MOD = 1e9 + 7;
const int maxn = 2e5 + 25;
ll dp[maxn];
signed main() { ios::sync_with_stdio(0); cin.tie(0);
    string s;
    cin >> s;
    int cnt = 0;
    vector<char> last;
    vector<pair<int, ll> > lastnode;
    vector<pair<int, ll> > stk;
    ll ans = 0;
    int firstcnt = 0;
    ll firstsum = 0;
    for(int i = 0; i < s.size(); ++i) {
        char c = s[i]; 
        if(c == '-') {
            if(last.back() == '(') stk.pop_back();
            else {
                if(!lastnode.empty()) {
                    if(!stk.empty()) {
                        stk.back().second -= dp[cnt];
                        --stk.back().first;
                        ans -= stk.back().first;
                    } else {
                        firstsum -= dp[cnt];
                        --firstcnt;
                        ans -= firstcnt; 
                    }
                    stk.push_back(lastnode.back());
                    lastnode.pop_back();
                    --ans;
                    dp[cnt--] = 0; 
                }
            } 
            last.pop_back();
            cout << ans << '\n';
            continue;
        }  
        last.push_back(c);
        if(c == '(') stk.push_back(make_pair(0, 0));
        else {
            if(!stk.empty()) {
                dp[++cnt] = 1 + stk.back().second + 1ll* (stk.back().first) * (stk.back().first - 1) / 2;
                ++ans;
                lastnode.push_back(stk.back());
                stk.pop_back();             
                if(!stk.empty()) {
                    ans += stk.back().first;
                    ++stk.back().first;
                    stk.back().second += dp[cnt];
                } else {
                    ans += firstcnt;
                    ++firstcnt;
                    firstsum += dp[cnt];
                }
            }
        }
        cout << ans << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

(()())---)

output:

0
0
1
1
3
4
3
1
1
2

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3408kb

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: 2ms
memory: 3584kb

input:

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

output:

0
0
0
0
0
0
1
1
1
2
2
2
2
2
1
1
1
2
2
2
2
4
6
4
4
4
5
5
7
7
7
10
7
5
5
5
6
7
9
12
9
7
7
9
9
9
9
10
11
10
11
11
11
12
12
12
13
15
15
15
15
18
20
23
25
25
25
25
25
25
25
26
26
26
26
27
27
29
29
32
32
36
37
39
37
37
37
38
40
40
40
40
40
40
40
41
44
41
41
43
46
43
46
46
46
46
46
43
46
48
49
50
50
50
50
...

result:

wrong answer 1207th numbers differ - expected: '773', found: '774'