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