fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define PI 3.14159265358979323846
  5. void*wmem;
  6. char memarr[96000000];
  7. template<class S, class T> inline S min_L(S a,T b){
  8.   return a<=b?a:b;
  9. }
  10. template<class S, class T> inline S max_L(S a,T b){
  11.   return a>=b?a:b;
  12. }
  13. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  14.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  15.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  16.   (*arr)=(T*)(*mem);
  17.   (*mem)=((*arr)+x);
  18. }
  19. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  20.   walloc1d(arr, x2-x1, mem);
  21.   (*arr) -= x1;
  22. }
  23. inline int my_getchar_unlocked(){
  24.   static char buf[1048576];
  25.   static int s = 1048576;
  26.   static int e = 1048576;
  27.   if(s == e && e == 1048576){
  28.     e = fread_unlocked(buf, 1, 1048576, stdin);
  29.     s = 0;
  30.   }
  31.   if(s == e){
  32.     return EOF;
  33.   }
  34.   return buf[s++];
  35. }
  36. inline void rd(char &c){
  37.   int i;
  38.   for(;;){
  39.     i = my_getchar_unlocked();
  40.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  41.       break;
  42.     }
  43.   }
  44.   c = i;
  45. }
  46. inline int rd(char c[]){
  47.   int i;
  48.   int sz = 0;
  49.   for(;;){
  50.     i = my_getchar_unlocked();
  51.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  52.       break;
  53.     }
  54.   }
  55.   c[sz++] = i;
  56.   for(;;){
  57.     i = my_getchar_unlocked();
  58.     if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
  59.       break;
  60.     }
  61.     c[sz++] = i;
  62.   }
  63.   c[sz]='\0';
  64.   return sz;
  65. }
  66. struct MY_WRITER{
  67.   char buf[1048576];
  68.   int s;
  69.   int e;
  70.   MY_WRITER(){
  71.     s = 0;
  72.     e = 1048576;
  73.   }
  74.   ~MY_WRITER(){
  75.     if(s){
  76.       fwrite_unlocked(buf, 1, s, stdout);
  77.     }
  78.   }
  79. }
  80. ;
  81. MY_WRITER MY_WRITER_VAR;
  82. void my_putchar_unlocked(int a){
  83.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  84.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  85.     MY_WRITER_VAR.s = 0;
  86.   }
  87.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  88. }
  89. inline void wt_L(char a){
  90.   my_putchar_unlocked(a);
  91. }
  92. inline void wt_L(long long x){
  93.   int s=0;
  94.   int m=0;
  95.   char f[20];
  96.   if(x<0){
  97.     m=1;
  98.     x=-x;
  99.   }
  100.   while(x){
  101.     f[s++]=x%10;
  102.     x/=10;
  103.   }
  104.   if(!s){
  105.     f[s++]=0;
  106.   }
  107.   if(m){
  108.     my_putchar_unlocked('-');
  109.   }
  110.   while(s--){
  111.     my_putchar_unlocked(f[s]+'0');
  112.   }
  113. }
  114. struct fft_pnt{
  115.   double x;
  116.   double y;
  117.   fft_pnt(void){
  118.   }
  119.   fft_pnt(double a, double b){
  120.     x = a;
  121.     y = b;
  122.   }
  123.   void set(double a, double b){
  124.     x = a;
  125.     y = b;
  126.   }
  127.   fft_pnt& operator+=(fft_pnt a){
  128.     x+=a.x;
  129.     y+=a.y;
  130.     return *this;
  131.   }
  132.   fft_pnt& operator-=(fft_pnt a){
  133.     x-=a.x;
  134.     y-=a.y;
  135.     return *this;
  136.   }
  137.   fft_pnt& operator*=(fft_pnt a){
  138.     fft_pnt p = *this;
  139.     x = p.x*a.x-p.y*a.y;
  140.     y = p.x*a.y+p.y*a.x;
  141.     return *this;
  142.   }
  143.   fft_pnt operator+(fft_pnt a){
  144.     return fft_pnt(*this) += a;
  145.   }
  146.   fft_pnt operator-(fft_pnt a){
  147.     return fft_pnt(*this) -= a;
  148.   }
  149.   fft_pnt operator*(fft_pnt a){
  150.     return fft_pnt(*this) *= a;
  151.   }
  152. }
  153. ;
  154. void fft_L(int n, fft_pnt x[], void *mem){
  155.   int i;
  156.   int j;
  157.   int n1;
  158.   int n2;
  159.   int n3;
  160.   int step = 1;
  161.   double theta = 2*PI / n;
  162.   double tmp;
  163.   fft_pnt w1;
  164.   fft_pnt w2;
  165.   fft_pnt w3;
  166.   fft_pnt a;
  167.   fft_pnt b;
  168.   fft_pnt c;
  169.   fft_pnt d;
  170.   fft_pnt aa;
  171.   fft_pnt bb;
  172.   fft_pnt cc;
  173.   fft_pnt dd;
  174.   fft_pnt*y = (fft_pnt*)mem;
  175.   while(n > 2){
  176.     n1 = n / 4;
  177.     n2 = n1 + n1;
  178.     n3 = n1 + n2;
  179.     for(i=(0);i<(n1);i++){
  180.       w1 = fft_pnt(cos(i*theta),-sin(i*theta));
  181.       w2 = w1*w1;
  182.       w3 = w1*w2;
  183.       for(j=(0);j<(step);j++){
  184.         a = x[j+step*i];
  185.         b = x[j+step*(i+n1)];
  186.         c = x[j+step*(i+n2)];
  187.         d = x[j+step*(i+n3)];
  188.         aa = a + c;
  189.         bb = a - c;
  190.         cc = b + d;
  191.         dd = b - d;
  192.         tmp = dd.y;
  193.         dd.y = dd.x;
  194.         dd.x = -tmp;
  195.         y[j+step*(4*i  )] = aa + cc;
  196.         y[j+step*(4*i+1)] = w1*(bb - dd);
  197.         y[j+step*(4*i+2)] = w2*(aa - cc);
  198.         y[j+step*(4*i+3)] = w3*(bb + dd);
  199.       }
  200.     }
  201.     n /= 4;
  202.     step *= 4;
  203.     theta *= 4;
  204.     swap(x,y);
  205.   }
  206.   if(n==2){
  207.     for(i=(0);i<(step);i++){
  208.       y[i] = x[i] + x[i+step];
  209.       y[i+step] = x[i] - x[i+step];
  210.     }
  211.     n /= 2;
  212.     step *= 2;
  213.     theta *= 2;
  214.     swap(x,y);
  215.   }
  216.   for(i=(0);i<(step);i++){
  217.     y[i] = x[i];
  218.   }
  219. }
  220. void fftinv_L(int n, fft_pnt x[], void *mem){
  221.   int i;
  222.   int j;
  223.   int n1;
  224.   int n2;
  225.   int n3;
  226.   int step = 1;
  227.   double theta = 2*PI / n;
  228.   double tmp;
  229.   fft_pnt w1;
  230.   fft_pnt w2;
  231.   fft_pnt w3;
  232.   fft_pnt a;
  233.   fft_pnt b;
  234.   fft_pnt c;
  235.   fft_pnt d;
  236.   fft_pnt aa;
  237.   fft_pnt bb;
  238.   fft_pnt cc;
  239.   fft_pnt dd;
  240.   fft_pnt*y = (fft_pnt*)mem;
  241.   while(n > 2){
  242.     n1 = n / 4;
  243.     n2 = n1 + n1;
  244.     n3 = n1 + n2;
  245.     for(i=(0);i<(n1);i++){
  246.       w1 = fft_pnt(cos(i*theta),sin(i*theta));
  247.       w2 = w1*w1;
  248.       w3 = w1*w2;
  249.       for(j=(0);j<(step);j++){
  250.         a = x[j+step*i];
  251.         b = x[j+step*(i+n1)];
  252.         c = x[j+step*(i+n2)];
  253.         d = x[j+step*(i+n3)];
  254.         aa = a + c;
  255.         bb = a - c;
  256.         cc = b + d;
  257.         dd = b - d;
  258.         tmp = dd.y;
  259.         dd.y = dd.x;
  260.         dd.x = -tmp;
  261.         y[j+step*(4*i  )] = aa + cc;
  262.         y[j+step*(4*i+1)] = w1*(bb + dd);
  263.         y[j+step*(4*i+2)] = w2*(aa - cc);
  264.         y[j+step*(4*i+3)] = w3*(bb - dd);
  265.       }
  266.     }
  267.     n /= 4;
  268.     step *= 4;
  269.     theta *= 4;
  270.     swap(x,y);
  271.   }
  272.   if(n==2){
  273.     for(i=(0);i<(step);i++){
  274.       y[i] = x[i] + x[i+step];
  275.       y[i+step] = x[i] - x[i+step];
  276.     }
  277.     n /= 2;
  278.     step *= 2;
  279.     theta *= 2;
  280.     swap(x,y);
  281.   }
  282.   for(i=(0);i<(step);i++){
  283.     y[i] = x[i];
  284.   }
  285. }
  286. void convolution_L(double A[], int As, double B[], int Bs, double res[], int Rs, void *mem = wmem){
  287.   int i;
  288.   int n;
  289.   int n2;
  290.   double mul;
  291.   fft_pnt*a;
  292.   fft_pnt*b;
  293.   n =max_L(As+Bs, Rs);
  294.   for(n2=1;n2<n;n2*=2){
  295.     ;
  296.   }
  297.   walloc1d(&a, n2, &mem);
  298.   walloc1d(&b, n2, &mem);
  299.   for(i=(0);i<(As);i++){
  300.     a[i].set(A[i], 0);
  301.   }
  302.   int jO2HaRTX = n2;
  303.   for(i=(As);i<(jO2HaRTX);i++){
  304.     a[i].set(0,0);
  305.   }
  306.   for(i=(0);i<(Bs);i++){
  307.     b[i].set(B[i], 0);
  308.   }
  309.   int n23oAcQn = n2;
  310.   for(i=(Bs);i<(n23oAcQn);i++){
  311.     b[i].set(0,0);
  312.   }
  313.   fft_L(n2, a, mem);
  314.   fft_L(n2, b, mem);
  315.   for(i=(0);i<(n2);i++){
  316.     a[i] *= b[i];
  317.   }
  318.   fftinv_L(n2, a, mem);
  319.   mul = 1.0 / n2;
  320.   for(i=(0);i<(Rs);i++){
  321.     res[i] = a[i].x * mul;
  322.   }
  323. }
  324. void convolution_L(double A[], int As, double res[], int Rs, void *mem = wmem){
  325.   int i;
  326.   int n;
  327.   int n2;
  328.   double mul;
  329.   fft_pnt*a;
  330.   n =max_L(As+As, Rs);
  331.   for(n2=1;n2<n;n2*=2){
  332.     ;
  333.   }
  334.   walloc1d(&a, n2, &mem);
  335.   for(i=(0);i<(As);i++){
  336.     a[i].set(A[i], 0);
  337.   }
  338.   int W9o_dQUM = n2;
  339.   for(i=(As);i<(W9o_dQUM);i++){
  340.     a[i].set(0,0);
  341.   }
  342.   fft_L(n2, a, mem);
  343.   for(i=(0);i<(n2);i++){
  344.     a[i] *= a[i];
  345.   }
  346.   fftinv_L(n2, a, mem);
  347.   mul = 1.0 / n2;
  348.   for(i=(0);i<(Rs);i++){
  349.     res[i] = a[i].x * mul;
  350.   }
  351. }
  352. int N;
  353. char S[500000+2];
  354. double a[500000+2];
  355. double c[500000+2];
  356. double t[1000000+2];
  357. int main(){
  358.   wmem = memarr;
  359.   int block = 5000;
  360.   int st;
  361.   int ed;
  362.   int i;
  363.   int j;
  364.   int len;
  365.   long long res = 0;
  366.   long long m;
  367.   N = rd(S);
  368.   for(st=(0);st<(N);st+=(block)){
  369.     ed =min_L(st+block, N);
  370.     len =min_L(st, N-ed)+ block;
  371.     for(i=(0);i<(len);i++){
  372.       a[i] = c[i] = 0;
  373.     }
  374.     for(i=(0);i<(len);i++){
  375.       if(st-len+i >= 0 && S[st-len+i]=='a'){
  376.         a[i]++;
  377.       }
  378.     }
  379.     for(i=(0);i<(len);i++){
  380.       if(st-len+i >= 0 && S[st-len+i]=='A'){
  381.         a[i]+=2;
  382.       }
  383.     }
  384.     for(i=(0);i<(len);i++){
  385.       if(ed+i < N && S[ed+i]=='c'){
  386.         c[i]++;
  387.       }
  388.     }
  389.     for(i=(0);i<(len);i++){
  390.       if(ed+i < N && S[ed+i]=='C'){
  391.         c[i]+=2;
  392.       }
  393.     }
  394.     convolution_L(a, len, c, len, t, 2*len);
  395.     for(i=(st);i<(ed);i++){
  396.       if(S[i]=='b' && 0 <= 2*i+len-st-ed  &&  2*i+len-st-ed < 2*len){
  397.         res += round(t[2*i+len-st-ed]);
  398.       }
  399.     }
  400.     for(i=(st);i<(ed);i++){
  401.       if(S[i]=='B' && 0 <= 2*i+len-st-ed  &&  2*i+len-st-ed < 2*len){
  402.         res += 2*round(t[2*i+len-st-ed]);
  403.       }
  404.     }
  405.     for(i=(st);i<(ed);i++){
  406.       if(S[i]=='b' || S[i]=='B'){
  407.         for(j=1;;j++){
  408.           if(i-j < 0 || i+j >= N){
  409.             break;
  410.           }
  411.           if(i-j < st && i+j >= ed){
  412.             break;
  413.           }
  414.           if(S[i-j]!='a' && S[i-j]!='A'){
  415.             continue;
  416.           }
  417.           if(S[i+j]!='c' && S[i+j]!='C'){
  418.             continue;
  419.           }
  420.           m = 1;
  421.           if(S[i]=='B'){
  422.             m*=2;
  423.           }
  424.           if(S[i-j]=='A'){
  425.             m*=2;
  426.           }
  427.           if(S[i+j]=='C'){
  428.             m*=2;
  429.           }
  430.           res += m;
  431.         }
  432.       }
  433.     }
  434.   }
  435.   wt_L(res);
  436.   wt_L('\n');
  437.   return 0;
  438. }
  439. // cLay varsion 20201102-1
  440.  
  441. // --- original code ---
  442. // int N;
  443. // char S[5d5+2];
  444. // double a[5d5+2], c[5d5+2], t[1d6+2];
  445. // {
  446. //   int block = 5000, st, ed, i, j, len;
  447. //   ll res = 0, m;
  448. //   rd(S@N);
  449. // 
  450. //   rep(st,0,N,block){
  451. //     ed = min(st+block, N);
  452. //     len = min(st, N-ed) + block;
  453. //     rep(i,len) a[i] = c[i] = 0;
  454. //     rep(i,len) if(st-len+i >= 0 && S[st-len+i]=='a') a[i]++;
  455. //     rep(i,len) if(st-len+i >= 0 && S[st-len+i]=='A') a[i]+=2;
  456. //     rep(i,len) if(ed+i < N && S[ed+i]=='c') c[i]++;
  457. //     rep(i,len) if(ed+i < N && S[ed+i]=='C') c[i]+=2;
  458. //     convolution(a, len, c, len, t, 2*len);
  459. //     rep(i,st,ed) if(S[i]=='b' && 0 <= 2*i+len-st-ed < 2*len) res += round(t[2*i+len-st-ed]);
  460. //     rep(i,st,ed) if(S[i]=='B' && 0 <= 2*i+len-st-ed < 2*len) res += 2*round(t[2*i+len-st-ed]);
  461. // 
  462. //     rep(i,st,ed) if(S[i]=='b' || S[i]=='B'){
  463. //       for(j=1;;j++){
  464. //         if(i-j < 0 || i+j >= N) break;
  465. //         if(i-j < st && i+j >= ed) break;
  466. //         if(S[i-j]!='a' && S[i-j]!='A') continue;
  467. //         if(S[i+j]!='c' && S[i+j]!='C') continue;
  468. //         m = 1;
  469. //         if(S[i]=='B') m*=2;
  470. //         if(S[i-j]=='A') m*=2;
  471. //         if(S[i+j]=='C') m*=2;
  472. //         res += m;
  473. //       }
  474. //     }
  475. //   }
  476. //   wt(res);
  477. // }
  478.  
Time limit exceeded #stdin #stdout 5s 4376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AuKWTn
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!