QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#162247 | #7106. Infinite Parenthesis Sequence | ucup-team1198# | AC ✓ | 1841ms | 24248kb | C++20 | 5.1kb | 2023-09-03 06:58:44 | 2023-09-03 06:58:45 |
Judging History
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