QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243028 | #7106. Infinite Parenthesis Sequence | wublabdubdub | RE | 0ms | 0kb | C++20 | 2.4kb | 2023-11-07 19:56:52 | 2023-11-07 19:56:53 |
answer
#include <iostream>
#include <cstdio>
using namespace std;
#define int long long
const long long inf = 2022102720221033LL;
const long long N = 1e5, M = 1e5;
char buf[1 << 21], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
long long rd()
{
long long res = 0, f = 1;
char ch;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
if (ch == '-')
f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
res = (res << 3) + (res << 1) + ch - '0';
return res * f;
}
void wt(int x, char ch = 0)
{
if (x < 0)
putchar('-'), wt(-x);
else
{
if (x >= 10)
wt(x / 10);
putchar(x % 10 + '0');
}
if (ch)
putchar(ch);
return;
}
string rdstr()
{
string s("");
char ch = getchar();
for (; ch != '(' && ch != ')'; ch = getchar());
for (; ch == '(' || ch == ')'; ch = getchar())
s.push_back(ch);
return s;
}
int lg[N], n, m;
string s;
int st[N][20];
void init()
{
m = 0;
for (int i = 0; i < n; i++)
if (s[i] == '(')
st[0][m++] = i;
for (int i = m; i < m * 2; i++)
st[0][i] = st[0][i - m] + n;
for (int i = 0; i < m * 2; i++)
st[0][i] -= i * 2;
for (int j = 1; (1 << j) < m*2; j++)
for (int i = 0; i + (1 << j) - 1 < m*2; i++)
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
return;
}
int calc(int K, int i)
{
int L, R;
if (m * 2 <= n)
{
L = i;
R = min(i + K, L + m - 1);
}
else
{
R = i + K;
L = max(i, R - m + 1);
}
int div = (L >= 0 ? L / m : (L + 1) / m - 1);
int mod = (L % m + m) % m;
int dlt = n * div - 2 * div * m;
int len = R - L + 1, s = lg[len];
return min(st[s][mod], st[s][mod + len - (1 << s)]) + dlt + K + 2 * i;
}
int query(int K, int lim)
{
int l =-inf , r = inf;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (calc(K, mid) <= lim)
l = mid;
else
r = mid - 1;
}
// cout<<l<<"!\n";
return l;
}
signed main()
{
// freopen("seq.in","r",stdin);
// freopen("seq.out","w",stdout);
for (int i = 2; i <= 1e5; i++)
lg[i] = lg[i / 2] + 1;
int T = rd();
while (T--)
{
// cout<<"T"<<T<<"\n";
s = rdstr();
// cout<<s<<"\n";
n = s.size();
init();
// cout<<m<<"\b";
int q = rd();
while (q--)
{
int K = rd(), l = rd(), r = rd();
if (m == 0)
wt(0, '\n');
else
wt(query(K, r) - query(K, l - 1),'\n');
}
}
// fclose(stdin);
// fclose(stdout);
return (0 - 0);
}
详细
Test #1:
score: 0
Runtime Error
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