QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243028#7106. Infinite Parenthesis SequencewublabdubdubRE 0ms0kbC++202.4kb2023-11-07 19:56:522023-11-07 19:56:53

Judging History

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

  • [2023-11-07 19:56:53]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-11-07 19:56:52]
  • 提交

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

output:


result: