QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#780412 | #1194. Parehtneses Editor | vwxyz | TL | 0ms | 0kb | C++23 | 3.1kb | 2024-11-25 10:49:10 | 2024-11-25 10:49:11 |
answer
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
// セグメントツリークラス
class SegmentTree {
using Func = function<int(int, int)>;
int n;
Func f;
int e;
vector<int> seg;
public:
SegmentTree(int N, Func func, int identity) : f(func), e(identity) {
n = 1;
while (n < N) n <<= 1;
seg.assign(2 * n, e);
}
void set(int i, int x) {
i += n;
seg[i] = x;
while (i > 1) {
i >>= 1;
seg[i] = f(seg[2 * i], seg[2 * i + 1]);
}
}
int fold(int l, int r) {
int vl = e, vr = e;
l += n;
r += n;
while (l < r) {
if (l & 1) vl = f(vl, seg[l++]);
if (r & 1) vr = f(seg[--r], vr);
l >>= 1;
r >>= 1;
}
return f(vl, vr);
}
int bisect_left(int r, function<bool(int)> cond) {
if (r == 0) return 0;
r += n;
int v = e;
int l = n;
while (l < r) {
if (l & 1) {
int tmp = f(v, seg[l]);
if (cond(tmp)) {
v = tmp;
l++;
} else {
while (l < n) {
l <<= 1;
tmp = f(v, seg[l]);
if (cond(tmp)) {
v = tmp;
l++;
}
}
return l - n;
}
}
l >>= 1;
}
return 0;
}
};
int main() {
string S;
cin >> S;
int N = S.size();
int M = 200000 + 10;
SegmentTree ST(N + 1, [](int a, int b) { return min(a, b); }, INF);
vector<int> queue = {0};
ST.set(0, 0);
long long ans = 0;
vector<vector<int>> lst(M * 2 + 10);
lst[M].push_back(0);
for (int i = 1; i <= N; ++i) {
char s = S[i - 1];
if (s == '(' || s == ')') {
if (s == '(') {
queue.push_back(queue.back() + 1);
lst[queue.back() + M].push_back(queue.size() - 1);
ST.set(queue.size() - 1, queue.back());
} else {
queue.push_back(queue.back() - 1);
lst[queue.back() + M].push_back(queue.size() - 1);
ST.set(queue.size() - 1, queue.back());
}
int l = ST.bisect_left(queue.size(), [&](int x) { return x >= queue.back(); });
ans += lst[queue.back() + M].size() - (lower_bound(lst[queue.back() + M].begin(), lst[queue.back() + M].end(), l) - lst[queue.back() + M].begin()) - 1;
} else {
int l = ST.bisect_left(queue.size(), [&](int x) { return x >= queue.back(); });
ans -= lst[queue.back() + M].size() - (lower_bound(lst[queue.back() + M].begin(), lst[queue.back() + M].end(), l) - lst[queue.back() + M].begin()) - 1;
lst[queue.back() + M].pop_back();
ST.set(queue.size() - 1, INF);
queue.pop_back();
}
cout << ans << "\n";
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
(()())---)