QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#260239 | #1194. Parehtneses Editor | lemonilemon# | WA | 2ms | 3584kb | C++20 | 2.1kb | 2023-11-21 22:48:05 | 2023-11-21 22:48:05 |
Judging History
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'