QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162247#7106. Infinite Parenthesis Sequenceucup-team1198#AC ✓1841ms24248kbC++205.1kb2023-09-03 06:58:442023-09-03 06:58:45

Judging History

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

  • [2023-09-03 06:58:45]
  • 评测
  • 测评结果:AC
  • 用时:1841ms
  • 内存:24248kb
  • [2023-09-03 06:58:44]
  • 提交

answer

#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

#define int int64_t

int norm(int x, int mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

struct InfArr {
    vector<int> val;
    vector<int> ind;
    int n;

    InfArr() {}

    int get_i_by_x(int x) {
        int rem = norm(x, n);
        int i = ind[rem];
        int k = (x - rem) / n;
        i += val.size() * k;
        return i;
    }

    int get_x_by_i(int i) {
        int rem = norm(i, val.size());
        int x = val[rem];
        int k = (i - rem) / (int)val.size();
        x += n * k;
        return x;
    }

    InfArr(string s) {
        n = s.size();
        ind.resize(n);
        for (int i = 0; i < n; ++i) {
            ind[i] = val.size();
            if (s[i] == ')') {
                val.push_back(i);
            }
        }
    }
};

const int MAXN = 1e5 + 100, MAXLN = 20;
int sp[MAXLN][MAXN], lg[MAXN];

const int INF = 1e9 + 100;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += (s[i] == '(');
    }
    if (cnt == 0 || cnt == n) {
        int q;
        cin >> q;
        while (q--) {
            int k, l, r;
            cin >> k >> l >> r;
            if (cnt == 0) {
                cout << "0\n";
            } else {
                cout << r - l + 1 << "\n";
            }
        }
        return;
    }
    InfArr arr1 = InfArr(s);
    string t = s;
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; ++i) {
        t[i] = '(' + ')' - t[i];
    }
    InfArr arr2 = InfArr(t);

    auto get_seg = [&](int x, int k) -> array<int, 2> {
        int id = arr1.get_i_by_x(x);
        id += k - 1;
        int r = arr1.get_x_by_i(id);
        id = arr2.get_i_by_x(n - x);
        id += k - 1;
        int l = n - arr2.get_x_by_i(id);
        return {l, r};
    };

    vector<int> bal(n, 0);
    for (int i = 1; i < n; ++i) {
        bal[i] = bal[i - 1];
        if (s[i - 1] == ')') {
            bal[i]--;
        } else {
            bal[i]++;
        }
    }
    int total = bal[n - 1];
    if (s[n - 1] == ')') {
        total--;
    } else {
        total++;
    }

    vector<int> pref(n + 1), suf(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = max(pref[i], bal[i]);
    }
    suf.back() = -INF;
    for (int i = n - 1; i >= 0; --i) {
        suf[i] = max(suf[i + 1], bal[i]);
    }

    for (int i = 0; i < n; ++i) {
        sp[0][i] = bal[i];
    }
    for (int lvl = 1; lvl < MAXLN; ++lvl) {
        for (int i = 0; i + (1 << lvl) <= n; ++i) {
            sp[lvl][i] = max(sp[lvl - 1][i], sp[lvl - 1][i + (1 << (lvl - 1))]);
        }
    }
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    auto get_sp = [&](int l, int r) {
        r++;
        int lvl = lg[r - l];
        return max(sp[lvl][l], sp[lvl][r - (1 << lvl)]);
    };

    auto get_max = [&](int l, int r) {
        int reml = norm(l, n), remr = norm(r, n);
        int kl = (l - reml) / n, kr = (r - remr) / n;
        if (kl == kr) {
            /// cerr << "here" << endl;
            int mx = get_sp(reml, remr);
            return mx + kl * total;
        }
        int mx = max(kl * total + suf[reml]
                   , kr * total + pref[remr + 1]);
        if (kr - kl > 1) {
            int all = suf[0];
            all += max(total * (kl + 1), total * (kr - 1));
            mx = max(mx, all);
        } 
        return mx;
    };

    auto get_bal = [&](int x) {
        int rem = norm(x, n);
        int k = (x - rem) / n;
        return bal[rem] + k * total;
    };

    auto count_op = [&](int x, int k) {
        auto res = get_seg(x, k);
        /**if (k == 2) {
            cerr << res[0] << " " << x << " " << res[1] << endl;
        }*/
        int mx = get_max(res[0], res[1]);
        /**if (k == 2) {
            cerr << mx << endl;
        }*/
        int cur = get_bal(x);
        /**if (k == 2) {
            cerr << cur << endl;
        }*/
        cur -= 2 * k - 1;
        return mx - cur;
    };

    auto get_val = [&](int x, int k) {
        int l = 0, r = k + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            int cnt = count_op(x, m);
            if (cnt <= k) {
                l = m;
            } else {
                r = m;
            }
        }
        /// cerr << x << " " << k << "->" << l << endl;
        return get_bal(x) - 2 * l;
    };

    int q;
    cin >> q;
    while (q--) {
        int k, l, r;
        cin >> k >> l >> r;
        ++r;
        if (k > n + 10) {
            int dif = k - (n + 10);
            k = n + 10;
            if (total > 0) {
                l += dif;
                r += dif;
            } else {
                l -= dif;
                r -= dif;
            }
        }
        int ans = get_val(r, k) - get_val(l, k);
        /// cerr << "!!!!" << endl;
        cout << (ans + r - l) / 2 << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5484kb

input:

3
(())
3
0 -3 2
1 -2 3
2 0 0
))()(
3
0 -3 4
2 1 3
3 -4 -1
))()(()(
4
1234 -5678 9012
123 -456 789
12 -34 56
1 -2 3

output:

3
3
0
4
1
1
7345
623
45
3

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 216ms
memory: 11848kb

input:

5564
()()(((()
16
0 -825489608 537105171
0 481386502 824237183
0 -32590250 515314371
0 -634830457 908018223
3 -494274112 299679416
125527658 81646800 208166552
632660143 -774899605 -551752339
4 -874787302 127206822
4 -102348267 122390255
2 -881139944 898929361
0 -656262874 -233671414
111787130 -5925...

output:

908396520
228567121
365269747
1028565788
529302353
84346502
148764845
667996084
149825682
1186712870
281727640
995600518
63752581
740373707
867951696
27044667
530591272
345487789
415550920
701803793
413364407
187916462
386485772
125057026
296666743
470522533
367131179
635722815
58970215
379425066
18...

result:

ok 271661 lines

Test #3:

score: 0
Accepted
time: 1708ms
memory: 23756kb

input:

7
((()(((()(((()((()((()((()(((()(((()((()(((()(((()((()(((()(((()(((()(((()((()(((()((()((()(((()(((()(((()((()((()(((()((()((()(((()(((()(((()((()(((()((()(((()((()((()(((()(((()(((()(((()((()(((()(((()((()((()((()(((()(((()((()(((()(((()(((()((()(((()(((()((()((()(((()(((()(((()((()((()(((()((()(...

output:

185704843
446800089
255099554
1156402
212636323
416191407
12472890
247228052
489620931
107469522
16222287
341270888
29184920
107393597
163613521
175919552
118376824
76183214
805506070
206363476
326077675
54361969
121810843
684646392
716061472
697723268
23956954
588434738
4870237
305505833
489380166
...

result:

ok 700000 lines

Test #4:

score: 0
Accepted
time: 1841ms
memory: 24248kb

input:

5571
()()(((()
16
0 -825489608 537105171
0 481386502 824237183
0 -32590250 515314371
0 -634830457 908018223
3 -494274112 299679416
125527658 81646800 208166552
632660143 -774899605 -551752339
4 -874787302 127206822
4 -102348267 122390255
2 -881139944 898929361
0 -656262874 -233671414
111787130 -5925...

output:

908396520
228567121
365269747
1028565788
529302353
84346502
148764845
667996084
149825682
1186712870
281727640
995600518
63752581
740373707
867951696
27044667
530591272
345487789
415550920
701803793
413364407
187916462
386485772
125057026
296666743
470522533
367131179
635722815
58970215
379425066
18...

result:

ok 971661 lines

Extra Test:

score: 0
Extra Test Passed