QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#303992 | #1194. Parehtneses Editor | NYCU_CartesianTree# | RE | 1ms | 7884kb | C++20 | 2.0kb | 2024-01-13 10:56:29 | 2024-01-13 10:56:29 |
Judging History
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:
))(((-)(()((---(-)(-())-(()()(-)--(())))--()((())-)(()(())((-))))(-(((()((()()()()))-(())((((--))-())-)(-(--))))((((-)(-(-)((((()--(---)(-))()(-)(()()-(())()(()()((()()))))(()(()(-(--)-()((()(((()-))-)(()-()()-(-((-)(-)(((()-)))))-())()-(()((()(-)()))((-))())))()()()(-(-(())-()(()-)-))((()))((--(-()...