fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. inline int my_getchar_unlocked(){
  5.   static char buf[1048576];
  6.   static int s = 1048576;
  7.   static int e = 1048576;
  8.   if(s == e && e == 1048576){
  9.     e = fread_unlocked(buf, 1, 1048576, stdin);
  10.     s = 0;
  11.   }
  12.   if(s == e){
  13.     return EOF;
  14.   }
  15.   return buf[s++];
  16. }
  17. inline void rd(int &x){
  18.   int k;
  19.   int m=0;
  20.   x=0;
  21.   for(;;){
  22.     k = my_getchar_unlocked();
  23.     if(k=='-'){
  24.       m=1;
  25.       break;
  26.     }
  27.     if('0'<=k&&k<='9'){
  28.       x=k-'0';
  29.       break;
  30.     }
  31.   }
  32.   for(;;){
  33.     k = my_getchar_unlocked();
  34.     if(k<'0'||k>'9'){
  35.       break;
  36.     }
  37.     x=x*10+k-'0';
  38.   }
  39.   if(m){
  40.     x=-x;
  41.   }
  42. }
  43. inline void rd(long long &x){
  44.   int k;
  45.   int m=0;
  46.   x=0;
  47.   for(;;){
  48.     k = my_getchar_unlocked();
  49.     if(k=='-'){
  50.       m=1;
  51.       break;
  52.     }
  53.     if('0'<=k&&k<='9'){
  54.       x=k-'0';
  55.       break;
  56.     }
  57.   }
  58.   for(;;){
  59.     k = my_getchar_unlocked();
  60.     if(k<'0'||k>'9'){
  61.       break;
  62.     }
  63.     x=x*10+k-'0';
  64.   }
  65.   if(m){
  66.     x=-x;
  67.   }
  68. }
  69. inline int rd_int(void){
  70.   int x;
  71.   rd(x);
  72.   return x;
  73. }
  74. struct MY_WRITER{
  75.   char buf[1048576];
  76.   int s;
  77.   int e;
  78.   MY_WRITER(){
  79.     s = 0;
  80.     e = 1048576;
  81.   }
  82.   ~MY_WRITER(){
  83.     if(s){
  84.       fwrite_unlocked(buf, 1, s, stdout);
  85.     }
  86.   }
  87. }
  88. ;
  89. MY_WRITER MY_WRITER_VAR;
  90. void my_putchar_unlocked(int a){
  91.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  92.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  93.     MY_WRITER_VAR.s = 0;
  94.   }
  95.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  96. }
  97. inline void wt_L(char a){
  98.   my_putchar_unlocked(a);
  99. }
  100. inline void wt_L(int x){
  101.   int s=0;
  102.   int m=0;
  103.   char f[10];
  104.   if(x<0){
  105.     m=1;
  106.     x=-x;
  107.   }
  108.   while(x){
  109.     f[s++]=x%10;
  110.     x/=10;
  111.   }
  112.   if(!s){
  113.     f[s++]=0;
  114.   }
  115.   if(m){
  116.     my_putchar_unlocked('-');
  117.   }
  118.   while(s--){
  119.     my_putchar_unlocked(f[s]+'0');
  120.   }
  121. }
  122. inline void wt_L(unsigned x){
  123.   int s=0;
  124.   char f[10];
  125.   while(x){
  126.     f[s++]=x%10;
  127.     x/=10;
  128.   }
  129.   if(!s){
  130.     f[s++]=0;
  131.   }
  132.   while(s--){
  133.     my_putchar_unlocked(f[s]+'0');
  134.   }
  135. }
  136. inline void wt_L(long long x){
  137.   int s=0;
  138.   int m=0;
  139.   char f[20];
  140.   if(x<0){
  141.     m=1;
  142.     x=-x;
  143.   }
  144.   while(x){
  145.     f[s++]=x%10;
  146.     x/=10;
  147.   }
  148.   if(!s){
  149.     f[s++]=0;
  150.   }
  151.   if(m){
  152.     my_putchar_unlocked('-');
  153.   }
  154.   while(s--){
  155.     my_putchar_unlocked(f[s]+'0');
  156.   }
  157. }
  158. inline void wt_L(unsigned long long x){
  159.   int s=0;
  160.   char f[21];
  161.   while(x){
  162.     f[s++]=x%10;
  163.     x/=10;
  164.   }
  165.   if(!s){
  166.     f[s++]=0;
  167.   }
  168.   while(s--){
  169.     my_putchar_unlocked(f[s]+'0');
  170.   }
  171. }
  172. int WRITER_DOUBLE_DIGIT = 15;
  173. inline int writerDigit_double(){
  174.   return WRITER_DOUBLE_DIGIT;
  175. }
  176. inline void writerDigit_double(int d){
  177.   WRITER_DOUBLE_DIGIT = d;
  178. }
  179. inline void wt_L(double x){
  180.   const int d = WRITER_DOUBLE_DIGIT;
  181.   int k;
  182.   int r;
  183.   double v;
  184.   if(x!=x || (x==x+1 && x==2*x)){
  185.     my_putchar_unlocked('E');
  186.     my_putchar_unlocked('r');
  187.     my_putchar_unlocked('r');
  188.     return;
  189.   }
  190.   if(x < 0){
  191.     my_putchar_unlocked('-');
  192.     x = -x;
  193.   }
  194.   x += 0.5 * pow(0.1, d);
  195.   r = 0;
  196.   v = 1;
  197.   while(x >= 10*v){
  198.     v *= 10;
  199.     r++;
  200.   }
  201.   while(r >= 0){
  202.     r--;
  203.     k = floor(x / v);
  204.     if(k >= 10){
  205.       k = 9;
  206.     }
  207.     if(k <= -1){
  208.       k = 0;
  209.     }
  210.     x -= k * v;
  211.     v *= 0.1;
  212.     my_putchar_unlocked(k + '0');
  213.   }
  214.   if(d > 0){
  215.     my_putchar_unlocked('.');
  216.     v = 1;
  217.     for(r=(0);r<(d);r++){
  218.       v *= 0.1;
  219.       k = floor(x / v);
  220.       if(k >= 10){
  221.         k = 9;
  222.       }
  223.       if(k <= -1){
  224.         k = 0;
  225.       }
  226.       x -= k * v;
  227.       my_putchar_unlocked(k + '0');
  228.     }
  229.   }
  230. }
  231. inline void wt_L(const char c[]){
  232.   int i=0;
  233.   for(i=0;c[i]!='\0';i++){
  234.     my_putchar_unlocked(c[i]);
  235.   }
  236. }
  237. inline void wt_L(string &x){
  238.   int i=0;
  239.   for(i=0;x[i]!='\0';i++){
  240.     my_putchar_unlocked(x[i]);
  241.   }
  242. }
  243. template<class T, class S> inline T pow_L(T a, S b){
  244.   T res = 1;
  245.   res = 1;
  246.   for(;;){
  247.     if(b&1){
  248.       res *= a;
  249.     }
  250.     b >>= 1;
  251.     if(b==0){
  252.       break;
  253.     }
  254.     a *= a;
  255.   }
  256.   return res;
  257. }
  258. inline double pow_L(double a, double b){
  259.   return pow(a,b);
  260. }
  261. int TEST;
  262. int sz;
  263. int d[20];
  264. long long dp[2];
  265. long long nx[2];
  266. long long solve(long long x){
  267.   int i, k;
  268.   long long res = 0;
  269.   if(x==0){
  270.     return res;
  271.   }
  272.   sz = 0;
  273.   while(x){
  274.     d[sz++] = x%10;
  275.     x/=10;
  276.   }
  277.   reverse(d, d+sz);
  278.   for(i=(1);i<(sz);i++){
  279.     res +=(pow_L(5LL,i));
  280.   }
  281.   {
  282.     auto cTE1_r3A = (0);
  283.     auto RZTsC2BF = ( 1);
  284.     dp[0] = cTE1_r3A;
  285.     dp[1] = RZTsC2BF;
  286.   }
  287.   for(k=(0);k<(sz);k++){
  288.     {
  289.       auto WYIGIcGE = (0);
  290.       auto t_ynMSdg = ( 0);
  291.       nx[0] = WYIGIcGE;
  292.       nx[1] = t_ynMSdg;
  293.     }
  294.     for(i=((k+1)%2);i<(10);i+=(2)){
  295.       nx[0] += dp[0];
  296.       if(i < d[k]){
  297.         nx[0] += dp[1];
  298.       }
  299.       if(i==d[k]){
  300.         nx[1] += dp[1];
  301.       }
  302.     }
  303.     {
  304.       auto tU__gIr_ = (nx[0]);
  305.       auto a2conNHc = ( nx[1]);
  306.       dp[0] = tU__gIr_;
  307.       dp[1] = a2conNHc;
  308.     }
  309.   }
  310.   return res + dp[0] + dp[1];
  311. }
  312. int main(){
  313.   int hCmBdyQB = rd_int();
  314.   for(TEST=(0);TEST<(hCmBdyQB);TEST++){
  315.     long long L;
  316.     rd(L);
  317.     long long R;
  318.     rd(R);
  319.     wt_L("Case #");
  320.     wt_L(TEST+1);
  321.     wt_L(": ");
  322.     wt_L(solve(R) - solve(L-1));
  323.     wt_L('\n');
  324.   }
  325.   return 0;
  326. }
  327. // cLay varsion 20201115-2
  328.  
  329. // --- original code ---
  330. // int TEST;
  331. // 
  332. // int sz, d[20];
  333. // ll dp[2], nx[2];
  334. // 
  335. // ll solve(ll x){
  336. //   ll res = 0;
  337. //   if(x==0) return res;
  338. // 
  339. //   sz = 0;
  340. //   while(x) d[sz++] = x%10, x/=10;
  341. //   reverse(d, d+sz);
  342. // 
  343. //   rep(i,1,sz) res += 5LL ** i;
  344. // 
  345. //   (dp[0], dp[1]) = (0, 1);
  346. //   rep(k,sz){
  347. //     (nx[0], nx[1]) = (0, 0);
  348. //     rep(i,(k+1)%2,10,2){
  349. //       nx[0] += dp[0];
  350. //       if(i < d[k]) nx[0] += dp[1];
  351. //       if(i==d[k]) nx[1] += dp[1];
  352. //     }
  353. //     (dp[0], dp[1]) = (nx[0], nx[1]);
  354. //   }
  355. // 
  356. //   return res + dp[0] + dp[1];
  357. // }
  358. // 
  359. // {
  360. //   REP(TEST,rd_int()){
  361. //     ll @L, @R;
  362. //     wtF("Case #{TEST+1}: ");
  363. //     wt(solve(R) - solve(L-1));
  364. //   }
  365. // }
  366.  
Time limit exceeded #stdin #stdout 5s 4372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PQQPp9
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!