QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66287 | #5014. 复读程度 | Minion# | 0 | 392ms | 6476kb | C++23 | 2.6kb | 2022-12-08 11:18:22 | 2024-05-26 01:07:45 |
Judging History
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()
{
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: 392ms
memory: 6340kb
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: 386ms
memory: 6476kb
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: 372ms
memory: 4436kb
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: 7
Accepted
time: 318ms
memory: 4492kb
input:
500 500 sulasusulasusulasulasulsulasusulasususulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasusulasusulasusulas...
output:
2320755102639148175 17108462705447992416 6030359132551843296 889683039894413148 10901851555398837076 1991544941914879425 9087724446342520941 5134546535199286414 12947484109492427089 5962550827492657739 4877066450610765849 6699323319072695780 11167645157062070624 13985172887966350800 8075429763917070...
result:
ok 500 lines
Test #5:
score: 0
Wrong Answer
time: 166ms
memory: 4296kb
input:
500 500 bbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrx...
output:
18295637548117042088 9063759256740399907 15681140870484623884 17957090271580958329 11763132903578154240 17769627666201366836 16493946443969420940 12712093409624537595 2436698665645215125 8863273927617841787 5065586857868462806 8771649105206144878 6715985691821336097 8851433094837196039 7055234226266...
result:
wrong answer 2nd lines differ - expected: '6105463594888898313', found: '9063759256740399907'
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%