QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66303 | #5014. 复读程度 | Minion# | 0 | 0ms | 0kb | C++23 | 2.8kb | 2022-12-08 11:31:58 | 2024-05-26 01:07:54 |
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];
W[l][r] = vl * vr;
fo(i,1,n - r + l) if(H(i,i + r - l) == H(l,r)) W[i][i + r - l] = W[l][r];
return W[l][r];
}
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] = (i << 1) + (gen() & 1);
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%