1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct Block {
    char type;
    long long len;
};

vector<Block> read_input() {
    int n;
    if (!(cin >> n)) return {};
    char c;
    cin >> c;
    vector<Block> blocks(n);
    for (int i = 0; i < n; i++) {
        long long length;
        cin >> length;
        blocks[i] = {c, length};
        c = (c == '(') ? ')' : '(';
    }
    return blocks;
}

int main() {
    vector<Block> s_blocks = read_input();
    vector<Block> t_blocks = read_input();

    if (s_blocks.empty() || t_blocks.empty()) return 0;

    long long s_bal = 0;
    long long s_min_bal = 0;
    long long s_max_bal = 0;

    for (auto b : s_blocks) {
        long long diff = (b.type == '(') ? b.len : -b.len;
        s_bal += diff;
        if (s_bal < s_min_bal) s_min_bal = s_bal;
        if (s_bal > s_max_bal) s_max_bal = s_bal;
    }

    long long target_balance = -s_bal;
    long long max_drop = s_max_bal;
    long long min_peak_needed = -s_min_bal;

    map<long long, long long> active_starts;
    map<long long, long long> pending_starts;

    long long current_t_bal = 0;
    long long valid_fragments = 0;

    if (min_peak_needed == 0) active_starts[0] = 1;
    else pending_starts[0] = 1;

    for (auto b : t_blocks) {
        for (long long step = 0; step < b.len; step++) { 
            
            if (b.type == '(') {
                current_t_bal++;
                
                long long activation_level = current_t_bal - min_peak_needed;
                if (pending_starts.count(activation_level)) {
                    active_starts[activation_level] += pending_starts[activation_level];
                    pending_starts.erase(activation_level);
                }

                long long looking_for = current_t_bal - target_balance;
                if (active_starts.count(looking_for)) {
                    valid_fragments += active_starts[looking_for];
                }

                if (min_peak_needed == 0) active_starts[current_t_bal]++;
                else pending_starts[current_t_bal]++;

            } else {
                current_t_bal--;

                long long death_level = current_t_bal + max_drop + 1;
                active_starts.erase(death_level);
                pending_starts.erase(death_level);

                long long looking_for = current_t_bal - target_balance;
                if (active_starts.count(looking_for)) {
                    valid_fragments += active_starts[looking_for];
                }

                if (min_peak_needed == 0) active_starts[current_t_bal]++;
                else pending_starts[current_t_bal]++;
            }
        }
    }

    cout << valid_fragments << "\n";
    return 0;
}