QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780420#1194. Parehtneses EditorvwxyzWA 2ms12468kbC++232.7kb2024-11-25 10:52:062024-11-25 10:52:07

Judging History

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

  • [2024-11-25 10:52:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12468kb
  • [2024-11-25 10:52:06]
  • 提交

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 = 0;
        while (l < n) {
            int tmp = f(v, seg[l + n]);
            if (cond(tmp)) break;
            v = tmp;
            ++l;
        }
        return l;
    }
};

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 12468kb

input:

(()())---)

output:

-1
-2
-3
-4
-5
-4
-5
-4
-3
-2

result:

wrong answer 1st numbers differ - expected: '0', found: '-1'