QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #877 | #580534 | #9372. Prefix of Suffixes | Bob_Wang | Bob_Wang | Success! | 2024-09-22 02:00:21 | 2024-09-22 02:00:21 |
详细
Extra Test:
Time Limit Exceeded
input:
300000 0 1 1 0 1 1 299998 1 1 299997 1 1 299994 1 1 299992 1 1 299988 1 1 299985 1 1 299980 1 1 299976 1 1 299970 1 1 299965 1 1 299958 1 1 299952 1 1 299944 1 1 299937 1 1 299928 1 1 299920 1 1 299910 1 1 299901 1 1 299890 1 1 299880 1 1 299868 1 1 299857 1 1 299844 1 1 299832 1 1 299818 1 1 299805...
output:
1 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81 90 100 110 121 132 144 156 169 182 196 210 225 240 256 272 289 306 324 342 361 380 400 420 441 462 484 506 529 552 576 600 625 650 676 702 729 756 784 812 841 870 900 930 961 992 1024 1056 1089 1122 1156 1190 1225 1260 1296 1332 1369 1406 1444 1482 1521 ...
result:
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #580534 | #9372. Prefix of Suffixes | Bob_Wang | TL | 66ms | 11012kb | C++17 | 774b | 2024-09-21 22:17:48 | 2024-09-23 01:38:04 |
answer
#include<cstdio>
#define maxn 300005
#define ll long long
using namespace std;
int n;
int fail[maxn],sum[maxn];
ll mod,lastans=0,totb,a[maxn],b[maxn],s[maxn];
void solve(int n)
{
scanf("%lld%lld%lld",&s[n],&a[n],&b[n]);
s[n]=(s[n]+lastans)%mod;
if(n==0)
fail[n+1]=0;
else
{
int t=fail[n];
while(t&&s[t]!=s[n])
t=fail[t];
fail[n+1]=((s[t]==s[n])?t+1:0);
}
if(fail[n+1]!=0)
sum[n]=sum[fail[n+1]-1]+1;
else sum[n]=1;
if(n>=1&&sum[n]!=sum[n-1]+1)
{
totb=0;
int t=n+1;
while(t)
{
int len=n-t+1;
totb+=b[len];
t=fail[t];
}
}
else totb+=b[n];
lastans+=totb*a[n];
printf("%lld\n",lastans);
}
int main()
{
fail[0]=0;
scanf("%d",&n);
mod=n;
for(int i=0;i<n;++i)
solve(i);
return 0;
}