QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#303992#1194. Parehtneses EditorNYCU_CartesianTree#RE 1ms7884kbC++202.0kb2024-01-13 10:56:292024-01-13 10:56:29

Judging History

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

  • [2024-01-13 10:56:29]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7884kb
  • [2024-01-13 10:56:29]
  • 提交

answer

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

#define int long long 
#define F first 
#define S second 
#define pb push_back

int mat[200005];
int preans[200005],block[200005],tra[200005];
void solve(){
    string a;
    cin>>a;

    vector<int>t1,t2;

    //t1 -> real
    //t2 -> wait to match

    int ans=0;
    for(int i=0;i<a.size();i++){
        if(a[i]=='('){
            t1.pb(a[i]);
            t2.pb(t1.size()-1);
            block[t1.size()-1]=0;
            tra[t1.size()-1]=0;
            preans[t1.size()-1]=0;
            mat[t1.size()-1]=0;
        }
        if(a[i]==')'){
            t1.pb(a[i]);
            block[t1.size()-1]=0;
            tra[t1.size()-1]=0;
            preans[t1.size()-1]=0;
            mat[t1.size()-1]=0;
            if(!t2.size()){
                tra[t1.size()-1]=1;
                cout<<ans<<"\n";
                continue;
            }
            int t=t2.back();t2.pop_back();
            mat[t1.size()-1]=t;
            preans[t]=ans;
            if(t==0){
                ans++;
                block[t1.size()-1]=1;
            }
            else{
                ans++;
                int q=block[t-1];
                block[t1.size()-1]=q+1;
                if(q>=2){
                    ans-=q*(q-1)/2;
                }
                ans+=(q+1)*q/2;
            }
        }
        if(a[i]=='-'){
            if(t1.back()=='('){
                t1.pop_back();
                t2.pop_back();
            }
            else{
                if(tra[t1.size()-1]) {
                    t1.pop_back();
                    t2.pop_back();
                }
                else{
                    ans=preans[mat[t1.size()-1]];
                    t2.pb(mat[t1.size()-1]);
                    t1.pop_back();
                }
            }
        }
        cout<<ans<<"\n";
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

详细

Test #1:

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

input:

(()())---)

output:

0
0
1
1
3
4
3
1
1
2

result:

ok 10 numbers

Test #2:

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

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
Runtime Error

input:

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

output:


result: