QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#66276#5014. 复读程度Minion#0 394ms4520kbC++232.6kb2022-12-08 11:14:232024-05-26 01:07:38

Judging History

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

  • [2024-05-26 01:07:38]
  • 评测
  • 测评结果:0
  • 用时:394ms
  • 内存:4520kb
  • [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:14:23]
  • 提交

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[21];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()
{
	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
Wrong Answer

Test #1:

score: 7
Accepted
time: 394ms
memory: 4428kb

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

15720454042420499810
4058077030882532408
14651762045124606089
4030024243931986061
18033423360813892607
9470601111824364484
3883374861354698625
16650831689368240202
8339028189650687576
2683289915379600554
13133811958066776394
14181220923901262251
18173739360450512256
13142314545999179754
148925491596...

result:

ok 500 lines

Test #2:

score: 7
Accepted
time: 389ms
memory: 4520kb

input:

500 500
zszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszz...

output:

4843650749197240262
7777110205341291111
533576317536031175
16712994243500559204
9988085877723856684
9644193924482321332
3247342125341043527
18152622312040037224
13045121434804725850
10593529771756855740
13316626648976199221
6181092693273210423
9148547538129213975
9376364571107435561
2140403332478526...

result:

ok 500 lines

Test #3:

score: 7
Accepted
time: 377ms
memory: 4520kb

input:

500 500
aaaaabbaabbabbbaabaabbabbabbbaaabaaaabbbbbbaaabaabbbbbbaabbaaaaababbaaaaabbbbababbabaabbbbbbbbaaaaaaabaabbabbbbaabbaabaaabbbabbaabbbabaabaaaaababbaabbabbbabbababbbaabbabaaabbbbaaabbbabbabaabbabbaaabbaabbabbbbaaaaaababaaaabaababbaabbabbabbbabbaabbbaabbaaababaaabbababbbabaababaabbbbbabbababaab...

output:

841375054012212333
13406426787139944226
6541986259052503362
10583258635957015782
11582649090627508617
4747829250201069768
11571422754704651998
14603866222879735665
8438246043626601023
16155298152184479844
9052925087624568857
18388444310571976215
13304308468056840286
18125780089857220122
363421144082...

result:

ok 500 lines

Test #4:

score: 0
Wrong Answer
time: 344ms
memory: 4352kb

input:

500 500
sulasusulasusulasulasulsulasusulasususulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasusulasusulasusulas...

output:

2320755102639148175
8278660392233389677
6030359132551843296
889683039894413148
1690158497847435811
1991544941914879425
15744286178433443627
8968187402233394037
12947484109492427089
5962550827492657739
4877066450610765849
6699323319072695780
11167645157062070624
13985172887966350800
80754297639170706...

result:

wrong answer 2nd lines differ - expected: '17108462705447992416', found: '8278660392233389677'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #22:

score: 0
Time Limit Exceeded

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%