Submission #1847672
Source Code Expand
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define next DCXISSOHANDSOME
#define ll long long
ll num[100010][26],next[100010],n,l,r,hh;
char s[200010];
inline ll rd()
{
ll x=0;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar());
for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x;
}
inline ll fib(ll len,ll x)
{
if (len<=n) return num[len][x];
if (len<=n+hh) return num[n][x]+num[len-n][x];
ll f1=num[n][x],f2=num[n][x]+num[hh][x],l1=n,l2=n+hh;
while (len>=l1+l2)
{
ll hhh=f2;f2+=f1;f1=hhh;
hhh=l2;l2+=l1;l1=hhh;
}
return f2+fib(len-l2,x);
}
inline ll calc(ll len,ll x)
{
if (len<=n) return num[len][x];
return fib(len,x);
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1)>>1;
l=rd();r=rd();
next[1]=0;
for (ll i=2;i<=n;i++)
{
ll j=next[i-1];
for (;j&&s[j+1]!=s[i];j=next[j]);
if (s[j+1]==s[i]) j++;
next[i]=j;
}
for (ll i=1;i<=n;i++)
{
for (ll j=0;j<26;j++) num[i][j]=num[i-1][j];
num[i][s[i]-'a']++;
}
hh=n-next[n];
for (ll i=0;i<26;i++) printf("%lld ",calc(r,i)-calc(l-1,i));
puts("");
return 0;
}
Submission Info
Submission Time
2017-12-10 12:30:32+0900
Task
F - SS
User
DCXDCX
Language
C++14 (GCC 5.4.1)
Score
1100
Code Size
1167 Byte
Status
AC
Exec Time
9 ms
Memory
21504 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:41:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s+1);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1100 / 1100
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt, sample3.txt
All
mx_100000_1_0.txt, rnd_6_16666_4.txt, rnd_7777_1_0.txt, rnd_7777_1_2289.txt, rnd_7777_1_6444.txt, rnd_7777_9_0.txt, rnd_7777_9_1542.txt, rnd_7777_9_2299.txt, rnd_77_1_0.txt, rnd_77_1_14.txt, rnd_77_1_2.txt, rnd_77_9_0.txt, rnd_77_9_11.txt, rnd_77_9_54.txt, rnd_7_1_0.txt, rnd_7_1_2.txt, rnd_7_1_3.txt, rnd_7_9_0.txt, rnd_7_9_1.txt, rnd_7_9_2.txt, rndmx_100000_1_0.txt, sample1.txt, sample2.txt, sample3.txt
Case Name
Status
Exec Time
Memory
mx_100000_1_0.txt
AC
9 ms
21504 KB
rnd_6_16666_4.txt
AC
8 ms
21504 KB
rnd_7777_1_0.txt
AC
2 ms
3456 KB
rnd_7777_1_2289.txt
AC
2 ms
3456 KB
rnd_7777_1_6444.txt
AC
2 ms
3456 KB
rnd_7777_9_0.txt
AC
6 ms
16384 KB
rnd_7777_9_1542.txt
AC
6 ms
16384 KB
rnd_7777_9_2299.txt
AC
6 ms
16384 KB
rnd_77_1_0.txt
AC
1 ms
256 KB
rnd_77_1_14.txt
AC
1 ms
256 KB
rnd_77_1_2.txt
AC
1 ms
256 KB
rnd_77_9_0.txt
AC
1 ms
384 KB
rnd_77_9_11.txt
AC
1 ms
384 KB
rnd_77_9_54.txt
AC
1 ms
384 KB
rnd_7_1_0.txt
AC
1 ms
256 KB
rnd_7_1_2.txt
AC
1 ms
256 KB
rnd_7_1_3.txt
AC
1 ms
256 KB
rnd_7_9_0.txt
AC
1 ms
256 KB
rnd_7_9_1.txt
AC
1 ms
256 KB
rnd_7_9_2.txt
AC
1 ms
256 KB
rndmx_100000_1_0.txt
AC
8 ms
21504 KB
sample1.txt
AC
1 ms
256 KB
sample2.txt
AC
1 ms
256 KB
sample3.txt
AC
1 ms
256 KB