QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#66283#5014. 复读程度Minion#0 0ms0kbC++232.7kb2022-12-08 11:17:222024-05-26 01:07:41

Judging History

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

  • [2024-05-26 01:07:41]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-08 11:17:22]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<utility>
#include<random>
#include<ctime>
#define fo(i,x,y) for(int i = x;i <= y;++i)
#define fd(i,x,y) for(int i = x;i >= y;--i)
#define _is 1048576 * 10
#define _os 1048576 * 2
#define gc() ib[++bi]
#define pc(ch) ob[++bo] = ch
#define ist(ch) (ch >= 'a' && ch <= 'z')
#define P pair<int,int>
#define u64 unsigned long long
#define p1 1000000007
#define p2 1000000009
using namespace std;
char ib[_is],ob[_os];int bi = -1,bo = -1;
u64 rd()
{
	u64 x = 0;char ch = gc();
	while(ch < 48 || ch > 57) ch = gc();
	while(ch >= 48 && ch <= 57) x = x * 10 + ch - 48,ch = gc();return x;
}
void gs(char *s)
{
	int l = -1;char ch = gc();
	while(ist(ch) == 0) ch = gc();
	while(ist(ch)) s[++l] = ch,ch = gc();
	s[++l] = 0;
}
void pr(u64 x)
{
	char ch[30];int w = -1;
	if(x == 0) ch[++w] = 48;
	while(x) ch[++w] = x % 10 + 48,x /= 10;
	fd(i,w,0) pc(ch[i]);pc('\n');
}
int n,q,l1,r1,l2,r2,L[100010],R[100010],v[30];
u64 wl[100010],wr[100010],W[5010][5010];
char s[100010];
P h[100010],mi[100010],imi[100010];
int ksm(int x,int y,int m)
{
	int res = 1;
	for(;y;y >>= 1,x = 1ll * x * x % m) if(y & 1) res = 1ll * res * x % m;
	return res;
}
int add(int x,int y,int m) {return x + y >= m ? x + y - m : x + y;}
P operator + (P a,P b) {return P(add(a.first,b.first,p1),add(a.second,b.second,p2));}
P operator - (P a,P b) {return P(add(a.first,p1 - b.first,p1),add(a.second,p2 - b.second,p2));}
P operator * (P a,P b) {return P(1ll * a.first * b.first % p1,1ll * a.second * b.second % p2);}
P H(int l,int r) {return (h[r] - h[l - 1]) * imi[l - 1];}
u64 w(int l,int r)
{
	if(W[l][r]) return W[l][r];
	u64 vl = 0,vr = 0;
	fo(i,1,n - r + l) if(H(i,i + r - l) == H(l,r)) vl += wl[i],vr += wr[i + r - l];
	return W[l][r] = vl * vr;
}
int main()
{
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	fread(ib,1,_is,stdin);
	n = rd(),q = rd(),gs(s + 1);
	fo(i,1,n) wl[i] = rd();
	fo(i,1,n) wr[i] = rd();
	mt19937 gen(time(0));
	fo(i,0,25) v[i] = gen() & 63;
	mi[0] = P(1,1),mi[1] = P(199,233),imi[0] = P(1,1),imi[1] = P(ksm(199,p1 - 2,p1),ksm(233,p2 - 2,p2));
	fo(i,2,n) mi[i] = mi[i - 1] * mi[1],imi[i] = imi[i - 1] * imi[1];
	fo(i,1,n) h[i] = h[i - 1] + mi[i] * P(v[s[i] - 97],v[s[i] - 97]);
	while(q--)
	{
		l1 = rd(),r1 = rd(),l2 = rd(),r2 = rd();
		int len = max(r1 - l1,r2 - l2) + 1;
		L[0] = R[0] = 0;
		fo(i,1,n - len + 1) if(H(i,i + r1 - l1) == H(l1,r1)) L[++L[0]] = i;
		fd(i,n,len) if(H(i - r2 + l2,i) == H(l2,r2)) R[++R[0]] = i;
		u64 ans = 0;
		fo(i,1,L[0]) fo(j,1,R[0])
		{
			if(R[j] - L[i] + 1 < len) break;
			ans += w(L[i],R[j]);
		}
		pr(ans);
	}
	fwrite(ob,1,bo + 1,stdout);
	return 0;
}

詳細信息

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Dangerous Syscalls

Test #22:

score: 0
Dangerous Syscalls

input:

100000 100000
zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%