fork download 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class T> struct cLtraits_identity{
  7.   using type = T;
  8. }
  9. ;
  10. template<class T> using cLtraits_try_make_signed =
  11.   typename conditional<
  12.     is_integral<T>::value,
  13.     make_signed<T>,
  14.     cLtraits_identity<T>
  15.     >::type;
  16. template<class T> using cLtraits_try_make_unsigned =
  17.   typename conditional<
  18.     is_integral<T>::value,
  19.     make_unsigned<T>,
  20.     cLtraits_identity<T>
  21.     >::type;
  22. template <class S, class T> struct cLtraits_common_type{
  23.   using tS = typename cLtraits_try_make_signed<S>::type;
  24.   using tT = typename cLtraits_try_make_signed<T>::type;
  25.   using type = typename common_type<tS,tT>::type;
  26. }
  27. ;
  28. void*wmem;
  29. char memarr[96000000];
  30. template<class S, class T> inline auto max_L(S a, T b)
  31. -> typename cLtraits_common_type<S,T>::type{
  32.   return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  33. }
  34. template<class S, class T> inline S chmin(S &a, T b){
  35.   if(a>b){
  36.     a=b;
  37.   }
  38.   return a;
  39. }
  40. template<class S, class T> inline S chmax(S &a, T b){
  41.   if(a<b){
  42.     a=b;
  43.   }
  44.   return a;
  45. }
  46. template<class S, class T> inline S divup_L(S a, T b){
  47.   return (a+b-1)/b;
  48. }
  49. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  50.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  51.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  52.   (*arr)=(T*)(*mem);
  53.   (*mem)=((*arr)+x);
  54. }
  55. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  56.   walloc1d(arr, x2-x1, mem);
  57.   (*arr) -= x1;
  58. }
  59. inline int Ilog2_f_L(const int n){
  60.   int res;
  61.   if(n <= 0){
  62.     return -1;
  63.   }
  64.   res = sizeof(int) * 8 - __builtin_clz(n) - 1;
  65.   return res;
  66. }
  67. inline int Ilog2_f_L(const long long n){
  68.   int res;
  69.   if(n <= 0){
  70.     return -1;
  71.   }
  72.   res = sizeof(long long) * 8 - __builtin_clzll(n) - 1;
  73.   return res;
  74. }
  75. template<class T1> void sortI(int N, T1 a[], void *mem = wmem){
  76.   sort(a, a+N);
  77. }
  78. template<class T1, class T2> void sortI(int N, T1 a[], T2 b[], void *mem = wmem){
  79.   int i;
  80.   pair<T1, T2>*arr;
  81.   walloc1d(&arr, N, &mem);
  82.   for(i=(0);i<(N);i++){
  83.     arr[i].first = a[i];
  84.     arr[i].second = b[i];
  85.   }
  86.   sort(arr, arr+N);
  87.   for(i=(0);i<(N);i++){
  88.     a[i] = arr[i].first;
  89.     b[i] = arr[i].second;
  90.   }
  91. }
  92. template<class T1, class T2, class T3> void sortI(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  93.   int i;
  94.   pair<T1, pair<T2, T3> >*arr;
  95.   walloc1d(&arr, N, &mem);
  96.   for(i=(0);i<(N);i++){
  97.     arr[i].first = a[i];
  98.     arr[i].second.first = b[i];
  99.     arr[i].second.second = c[i];
  100.   }
  101.   sort(arr, arr+N);
  102.   for(i=(0);i<(N);i++){
  103.     a[i] = arr[i].first;
  104.     b[i] = arr[i].second.first;
  105.     c[i] = arr[i].second.second;
  106.   }
  107. }
  108. template<class T1, class T2, class T3, class T4> void sortI(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem = wmem){
  109.   int i;
  110.   pair<pair<T1, T2>, pair<T3, T4> >*arr;
  111.   walloc1d(&arr, N, &mem);
  112.   for(i=(0);i<(N);i++){
  113.     arr[i].first.first = a[i];
  114.     arr[i].first.second = b[i];
  115.     arr[i].second.first = c[i];
  116.     arr[i].second.second = d[i];
  117.   }
  118.   sort(arr, arr+N);
  119.   for(i=(0);i<(N);i++){
  120.     a[i] = arr[i].first.first;
  121.     b[i] = arr[i].first.second;
  122.     c[i] = arr[i].second.first;
  123.     d[i] = arr[i].second.second;
  124.   }
  125. }
  126. template<class T> inline int sort_helper_getbit(T A[]){
  127.   return -1;
  128. }
  129. template<> inline int sort_helper_getbit(int A[]){
  130.   return sizeof(int)*8;
  131. }
  132. template<> inline int sort_helper_getbit(unsigned A[]){
  133.   return sizeof(unsigned)*8;
  134. }
  135. template<> inline int sort_helper_getbit(long long A[]){
  136.   return sizeof(long long)*8;
  137. }
  138. template<> inline int sort_helper_getbit(unsigned long long A[]){
  139.   return sizeof(unsigned long long)*8;
  140. }
  141. template<> inline int sort_helper_getbit(char A[]){
  142.   return sizeof(char)*8;
  143. }
  144. template<class T> void sortA_1_int_L(int N, T A[], void *mem = wmem){
  145.   int i;
  146.   int j;
  147.   int k;
  148.   int b;
  149.   int s;
  150.   int ok;
  151.   ok = 1;
  152.   for(i=(1);i<(N);i++){
  153.     if(A[i-1] > A[i]){
  154.       ok = 0;
  155.       break;
  156.     }
  157.   }
  158.   if(ok){
  159.     return;
  160.   }
  161.   if(N < 128){
  162.     sort(A,A+N);
  163.     return;
  164.   }
  165.   b = sort_helper_getbit(A);
  166.   if(b==-1){
  167.     sort(A,A+N);
  168.     return;
  169.   }
  170.   T mn;
  171.   T mx;
  172.   mn = mx = A[0];
  173.   for(i=(1);i<(N);i++){
  174.     chmin(mn, A[i]);
  175.   }
  176.   for(i=(1);i<(N);i++){
  177.     chmax(mx, A[i]);
  178.   }
  179.   ok = 1;
  180.   if(mn < 0 && mx > 0 && (mn < -N || mx > N)){
  181.     ok = 0;
  182.   }
  183.   if(ok && mx - mn > N){
  184.     ok = 0;
  185.   }
  186.   if(ok){
  187.     int*tmp;
  188.     walloc1d(&tmp, mx-mn+1, &mem);
  189.     for(i=(0);i<(mx-mn+1);i++){
  190.       tmp[i] = 0;
  191.     }
  192.     for(i=(0);i<(N);i++){
  193.       tmp[A[i]-mn]++;
  194.     }
  195.     k = 0;
  196.     for(i=(0);i<(mx-mn+1);i++){
  197.       while(tmp[i] > 0){
  198.         tmp[i]--;
  199.         A[k++] = i+mn;
  200.       }
  201.     }
  202.     return;
  203.   }
  204.   {
  205.     typename make_unsigned<T>::type *t[2];
  206.     typename make_unsigned<T>::type  mask;
  207.     typename make_unsigned<T>::type  cur;
  208.     typename make_unsigned<T>::type  one = 1;
  209.     T tone = 1;
  210.     int*pos;
  211.     int nn = 0;
  212.     int ss;
  213.     s =Ilog2_f_L(N);
  214.     if(s > 8){
  215.       s = (8 + (s-7)/2);
  216.     }
  217.     ss = 1;
  218.     for(;;){
  219.       if(ss >= b){
  220.         break;
  221.       }
  222.       if( mx >= 0 && (tone << (ss-1)) < mx ){
  223.         ss++;
  224.         continue;
  225.       }
  226.       if( mn < 0 && -(tone << (ss-1)) >= mn ){
  227.         ss++;
  228.         continue;
  229.       }
  230.       break;
  231.     }
  232.     k =(divup_L(ss,s));
  233.     s =(divup_L(ss,k));
  234.     mask = 0;
  235.     for(i=(0);i<(b);i++){
  236.       if(i < s*k){
  237.         mask |= one << i;
  238.       }
  239.     }
  240.     t[0] = (typename make_unsigned<T>::type *) A;
  241.     walloc1d(&t[1], N, &mem);
  242.     walloc1d(&pos, (1<<s)+1, &mem);
  243.     for(j=(0);j<(k);j++){
  244.       cur = 0;
  245.       for(i=(0);i<(b);i++){
  246.         if(s*j <= i && i < s*(j+1) && i < b){
  247.           cur |= one << i;
  248.         }
  249.       }
  250.       for(i=(0);i<((1<<s)+1);i++){
  251.         pos[i] = 0;
  252.       }
  253.       for(i=(0);i<(N);i++){
  254.         pos[((t[nn][i]&cur)>>(s*j))+1]++;
  255.       }
  256.       for(i=(0);i<((1<<s));i++){
  257.         pos[i+1] += pos[i];
  258.       }
  259.       for(i=(0);i<(N);i++){
  260.         t[nn^1][pos[(t[nn][i]&cur)>>(s*j)]++] = t[nn][i];
  261.       }
  262.       nn ^= 1;
  263.       mask ^= cur;
  264.     }
  265.     if(mn < 0 && mx >= 0){
  266.       k = 0;
  267.       for(i=(0);i<(N);i++){
  268.         if(A[i] < 0){
  269.           k++;
  270.         }
  271.       }
  272.       for(i=(0);i<(k);i++){
  273.         t[nn^1][i] = t[nn][N-k+i];
  274.       }
  275.       for(i=(k);i<(N);i++){
  276.         t[nn^1][i] = t[nn][i-k];
  277.       }
  278.       nn ^= 1;
  279.     }
  280.     if(nn==1){
  281.       for(i=(0);i<(N);i++){
  282.         t[0][i] = t[1][i];
  283.       }
  284.     }
  285.     return;
  286.   }
  287.   sort(A, A+N);
  288. }
  289. template<class T> void sortA_1_nonint_L(int N, T A[], void *mem = wmem){
  290.   sort(A,A+N);
  291. }
  292. template<class T> void sortA_1_call_L(int N, T A[], void *mem = wmem){
  293.   sortA_1_nonint_L(N, A, mem);
  294. }
  295. template<> void sortA_1_call_L(int N, int A[], void *mem){
  296.   sortA_1_int_L(N, A, mem);
  297. }
  298. template<> void sortA_1_call_L(int N, unsigned A[], void *mem){
  299.   sortA_1_int_L(N, A, mem);
  300. }
  301. template<> void sortA_1_call_L(int N, long long A[], void *mem){
  302.   sortA_1_int_L(N, A, mem);
  303. }
  304. template<> void sortA_1_call_L(int N, unsigned long long A[], void *mem){
  305.   sortA_1_int_L(N, A, mem);
  306. }
  307. template<> void sortA_1_call_L(int N, char A[], void *mem){
  308.   sortA_1_int_L(N, A, mem);
  309. }
  310. template<class T1> void sortA(int N, T1 a[], void *mem = wmem){
  311.   sortA_1_call_L(N, a, mem);
  312. }
  313. template<class T1, class T2> void sortA_2_int_L(int N, T1 A[], T2 B[], void *mem = wmem){
  314.   int i;
  315.   int b_a;
  316.   int b_b;
  317.   int s1;
  318.   int s2;
  319.   int so2;
  320.   T1 mn1;
  321.   T1 mx1;
  322.   T2 mn2;
  323.   T2 mx2;
  324.   typename cLtraits_try_make_unsigned<T1>::type r1;
  325.   typename cLtraits_try_make_unsigned<T2>::type r2;
  326.   so2 = 1;
  327.   for(i=(1);i<(N);i++){
  328.     if(A[i-1] > A[i] || (A[i-1]==A[i] && B[i-1] > B[i])){
  329.       so2 = 0;
  330.       break;
  331.     }
  332.   }
  333.   if(so2){
  334.     return;
  335.   }
  336.   so2 = 1;
  337.   for(i=(1);i<(N);i++){
  338.     if(A[i-1] > A[i]){
  339.       so2 = 0;
  340.       break;
  341.     }
  342.   }
  343.   if(so2==1){
  344.     int k = 0;
  345.     for(i=(1);i<(N);i++){
  346.       if(A[i] != A[i-1]){
  347.         sortA_1_call_L(i-k, B+k, mem);
  348.         k = i;
  349.       }
  350.     }
  351.     sortA_1_call_L(N-k, B+k, mem);
  352.     return;
  353.   }
  354.   if(N < 128){
  355.     sortI(N,A,B,mem);
  356.     return;
  357.   }
  358.   b_a = sort_helper_getbit(A);
  359.   b_b = sort_helper_getbit(B);
  360.   if(b_a == -1 || b_b == -1){
  361.     sortI(N,A,B,mem);
  362.     return;
  363.   }
  364.   mn1 = mx1 = A[0];
  365.   for(i=(1);i<(N);i++){
  366.     chmin(mn1, A[i]);
  367.   }
  368.   for(i=(1);i<(N);i++){
  369.     chmax(mx1, A[i]);
  370.   }
  371.   mn2 = mx2 = B[0];
  372.   for(i=(1);i<(N);i++){
  373.     chmin(mn2, B[i]);
  374.   }
  375.   for(i=(1);i<(N);i++){
  376.     chmax(mx2, B[i]);
  377.   }
  378.   if(mn1 < -4611686016279904256LL || mn2 < -4611686016279904256LL || mx1 > 4611686016279904256LL || mx2 > 4611686016279904256LL || mx1-mn1 > 4611686016279904256LL || mx2-mn2 > 4611686016279904256LL){
  379.     sortI(N,A,B,mem);
  380.     return;
  381.   }
  382.   r1 = (typename cLtraits_try_make_unsigned<T1>::type)(mx1) - (typename cLtraits_try_make_unsigned<T1>::type)(mn1);
  383.   r2 = (typename cLtraits_try_make_unsigned<T2>::type)(mx2) - (typename cLtraits_try_make_unsigned<T2>::type)(mn2);
  384.   if(r1 == 0){
  385.     sortA_1_call_L(N, B, mem);
  386.     return;
  387.   }
  388.   if(r2 == 0){
  389.     sortA_1_call_L(N, A, mem);
  390.     return;
  391.   }
  392.   if(r1 <= N){
  393.     so2 = 1;
  394.     for(i=(1);i<(N);i++){
  395.       if(B[i-1] > B[i]){
  396.         so2 = 0;
  397.         break;
  398.       }
  399.     }
  400.     if(so2 == 1){
  401.       T1*aa;
  402.       T2*bb;
  403.       int*pos;
  404.       int k;
  405.       walloc1d(&aa,N,&mem);
  406.       walloc1d(&bb,N,&mem);
  407.       walloc1d(&pos,r1+2,&mem);
  408.       for(i=(0);i<(r1+2);i++){
  409.         pos[i] = 0;
  410.       }
  411.       for(i=(0);i<(N);i++){
  412.         aa[i] = A[i];
  413.       }
  414.       for(i=(0);i<(N);i++){
  415.         bb[i] = B[i];
  416.       }
  417.       for(i=(0);i<(N);i++){
  418.         pos[(typename cLtraits_try_make_unsigned<T1>::type)((typename cLtraits_try_make_unsigned<T1>::type)aa[i]-(typename cLtraits_try_make_unsigned<T1>::type)mn1)+1]++;
  419.       }
  420.       for(i=(1);i<(r1+2);i++){
  421.         pos[i] += pos[i-1];
  422.       }
  423.       for(i=(0);i<(N);i++){
  424.         k = pos[(typename cLtraits_try_make_unsigned<T1>::type)((typename cLtraits_try_make_unsigned<T1>::type)aa[i]-(typename cLtraits_try_make_unsigned<T1>::type)mn1)+0]++;
  425.         A[k] = aa[i];
  426.         B[k] = bb[i];
  427.       }
  428.       return;
  429.     }
  430.   }
  431.   s1 = s2 = 1;
  432.   while( s1 < 64 && r1 >= (1ULL<<s1) ){
  433.     s1++;
  434.   }
  435.   while( s2 < 64 && r2 >= (1ULL<<s2) ){
  436.     s2++;
  437.   }
  438.   if(s1 + s2 <= 32){
  439.     unsigned*tmp;
  440.     walloc1d(&tmp,N,&mem);
  441.     for(i=(0);i<(N);i++){
  442.       tmp[i] = (((unsigned)((int)A[i]-(int)mn1)) << s2) | ((unsigned)((int)B[i]-(int)mn2));
  443.     }
  444.     sortA_1_call_L(N, tmp, mem);
  445.     for(i=(0);i<(N);i++){
  446.       A[i] = ((int)(tmp[i] >> s2)) + ((int)mn1);
  447.       B[i] = ((int)(tmp[i] & ((1U<<s2)-1))) + ((int)mn2);
  448.     }
  449.     return;
  450.   }
  451.   if(s1 + s2 <= 64){
  452.     unsigned long long*tmp;
  453.     walloc1d(&tmp,N,&mem);
  454.     for(i=(0);i<(N);i++){
  455.       tmp[i] = (((unsigned long long)((long long)A[i]-(long long)mn1)) << s2) | ((unsigned long long)((long long)B[i]-(long long)mn2));
  456.     }
  457.     sortA_1_call_L(N, tmp, mem);
  458.     for(i=(0);i<(N);i++){
  459.       A[i] = ((long long)(tmp[i] >> s2)) + ((long long)mn1);
  460.       B[i] = ((long long)(tmp[i] & ((1ULL<<s2)-1))) + ((long long)mn2);
  461.     }
  462.     return;
  463.   }
  464.   sortI(N,A,B,mem);
  465. }
  466. template<class T1, class T2> void sortA_2_nonint_L(int N, T1 A[], T2 B[], void *mem = wmem){
  467.   sortI(N,A,B,mem);
  468. }
  469. template<class T1, class T2> void sortA_2_call_L(int N, T1 A[], T2 B[], void *mem = wmem){
  470.   sortA_2_nonint_L(N, A, B, mem);
  471. }
  472. template<class T2> void sortA_2_call_L(int N, int A[], T2 B[], void *mem){
  473.   sortA_2_int_L(N, A, B, mem);
  474. }
  475. template<class T2> void sortA_2_call_L(int N, unsigned A[], T2 B[], void *mem){
  476.   sortA_2_int_L(N, A, B, mem);
  477. }
  478. template<class T2> void sortA_2_call_L(int N, long long A[], T2 B[], void *mem){
  479.   sortA_2_int_L(N, A, B, mem);
  480. }
  481. template<class T2> void sortA_2_call_L(int N, unsigned long long A[], T2 B[], void *mem){
  482.   sortA_2_int_L(N, A, B, mem);
  483. }
  484. template<class T2> void sortA_2_call_L(int N, char A[], T2 B[], void *mem){
  485.   sortA_2_int_L(N, A, B, mem);
  486. }
  487. template<class T1, class T2> void sortA(int N, T1 a[], T2 b[], void *mem = wmem){
  488.   sortA_2_call_L(N, a, b, mem);
  489. }
  490. template<class T1, class T2, class T3> void sortA(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  491.   int i;
  492.   pair<T1, pair<T2, T3> >*arr;
  493.   walloc1d(&arr, N, &mem);
  494.   for(i=(0);i<(N);i++){
  495.     arr[i].first = a[i];
  496.     arr[i].second.first = b[i];
  497.     arr[i].second.second = c[i];
  498.   }
  499.   sort(arr, arr+N);
  500.   for(i=(0);i<(N);i++){
  501.     a[i] = arr[i].first;
  502.     b[i] = arr[i].second.first;
  503.     c[i] = arr[i].second.second;
  504.   }
  505. }
  506. template<class T1, class T2, class T3, class T4> void sortA(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem = wmem){
  507.   int i;
  508.   pair<pair<T1, T2>, pair<T3, T4> >*arr;
  509.   walloc1d(&arr, N, &mem);
  510.   for(i=(0);i<(N);i++){
  511.     arr[i].first.first = a[i];
  512.     arr[i].first.second = b[i];
  513.     arr[i].second.first = c[i];
  514.     arr[i].second.second = d[i];
  515.   }
  516.   sort(arr, arr+N);
  517.   for(i=(0);i<(N);i++){
  518.     a[i] = arr[i].first.first;
  519.     b[i] = arr[i].first.second;
  520.     c[i] = arr[i].second.first;
  521.     d[i] = arr[i].second.second;
  522.   }
  523. }
  524. template<class T1, class T2> void sortA_index(int N, T1 a[], T2 b[], void *mem = wmem){
  525.   int i;
  526.   for(i=(0);i<(N);i++){
  527.     b[i] = i;
  528.   }
  529.   sortA(N,a,b,mem);
  530. }
  531. template<class T1, class T2, class T3> void sortA_index(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  532.   int i;
  533.   for(i=(0);i<(N);i++){
  534.     c[i] = i;
  535.   }
  536.   sortA(N,a,b,c,mem);
  537. }
  538. template<class T1, class T2, class T3, class T4> void sortA_index(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem = wmem){
  539.   int i;
  540.   for(i=(0);i<(N);i++){
  541.     d[i] = i;
  542.   }
  543.   sortA(N,a,b,c,d,mem);
  544. }
  545. template<class T> struct segtree_Point_Maxval{
  546.   int N;
  547.   int logN;
  548.   T*mx;
  549.   void malloc(int maxN, int once = 0){
  550.     int i;
  551.     for(i=1;i<maxN;i*=2){
  552.       ;
  553.     }
  554.     mx = new T[2*i];
  555.     if(once){
  556.       setN(maxN);
  557.     }
  558.   }
  559.   void walloc(int maxN, int once = 0, void **mem = &wmem){
  560.     int i;
  561.     for(i=1;i<maxN;i*=2){
  562.       ;
  563.     }
  564.     walloc1d(&mx, 2*i, mem);
  565.     if(once){
  566.       setN(maxN);
  567.     }
  568.   }
  569.   void free(void){
  570.     delete [] mx;
  571.   }
  572.   T& operator[](int i){
  573.     return mx[N+i];
  574.   }
  575.   void setN(int n, int zerofill = 1, int dobuild = 1){
  576.     int i;
  577.     for(i=1,logN=0;i<n;i*=2,logN++){
  578.       ;
  579.     }
  580.     N = i;
  581.     if(zerofill){
  582.       for(i=(0);i<(N);i++){
  583.         mx[N+i] = 0;
  584.       }
  585.     }
  586.     if(dobuild){
  587.       build();
  588.     }
  589.   }
  590.   void build(void){
  591.     int i;
  592.     for(i=N-1;i;i--){
  593.       mx[i] =max_L(mx[2*i], mx[2*i+1]);
  594.     }
  595.   }
  596.   inline void build(int a){
  597.     while(a > 1){
  598.       a /= 2;
  599.       mx[a] =max_L(mx[2*a], mx[2*a+1]);
  600.     }
  601.   }
  602.   inline void change(int a, T val){
  603.     mx[a+N] = val;
  604.     build(a+N);
  605.   }
  606.   inline void add(int a, T val){
  607.     mx[a+N] += val;
  608.     build(a+N);
  609.   }
  610.   inline T getMaxVal(int a, int b){
  611.     T res;
  612.     T tmp;
  613.     int fga = 0;
  614.     int fgb = 0;
  615.     a += N;
  616.     b += N;
  617.     while(a < b){
  618.       if(a%2){
  619.         if(fga){
  620.           res =max_L(res, mx[a]);
  621.         }
  622.         else{
  623.           res = mx[a];
  624.           fga = 1;
  625.         }
  626.         a++;
  627.       }
  628.       if(b%2){
  629.         b--;
  630.         if(fgb){
  631.           tmp =max_L(mx[b], tmp);
  632.         }
  633.         else{
  634.           tmp = mx[b];
  635.           fgb = 1;
  636.         }
  637.       }
  638.       a /= 2;
  639.       b /= 2;
  640.     }
  641.     if(fga==1 && fgb==0){
  642.       return res;
  643.     }
  644.     if(fga==0 && fgb==1){
  645.       return tmp;
  646.     }
  647.     if(fga==1 && fgb==1){
  648.       res =max_L(res, tmp);
  649.       return res;
  650.     }
  651.     return res;
  652.   }
  653. }
  654. ;
  655. template<class T, class S> inline int vec2arr(vector<T> &v, S arr[]){
  656.   int i;
  657.   int N = v.size();
  658.   for(i=(0);i<(N);i++){
  659.     arr[i] = v[i];
  660.   }
  661.   return N;
  662. }
  663. template<class T, class S1, class S2> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[]){
  664.   int i;
  665.   int N = v.size();
  666.   for(i=(0);i<(N);i++){
  667.     arr1[i] = v[i][0];
  668.     arr2[i] = v[i][1];
  669.   }
  670.   return N;
  671. }
  672. template<class T, class S1, class S2, class S3> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[], S3 arr3[]){
  673.   int i;
  674.   int N = v.size();
  675.   for(i=(0);i<(N);i++){
  676.     arr1[i] = v[i][0];
  677.     arr2[i] = v[i][1];
  678.     arr3[i] = v[i][2];
  679.   }
  680.   return N;
  681. }
  682. #define main dummy_main
  683. int main(){
  684.   wmem = memarr;
  685.   return 0;
  686. }
  687. #undef main
  688. class Solution{
  689.   public:
  690.   long long maxBalancedSubsequenceSum(vector<int> &nums){
  691.     int i;
  692.     dummy_main();
  693.     static int N;
  694.     static int A[100000];
  695.     static int ind[100000];
  696.     segtree_Point_Maxval<long long> t;
  697.     long long res = 0;
  698.     long long tmp;
  699.     N = vec2arr(nums, A);
  700.     int Nzj9Y0kE;
  701.     cLtraits_try_make_signed<remove_reference<decltype((*((int*)NULL)))>::type>::type bkxOPzPX;
  702.     if(N==0){
  703.       bkxOPzPX = 0;
  704.     }
  705.     else{
  706.       bkxOPzPX = A[0];
  707.       for(Nzj9Y0kE=(1);Nzj9Y0kE<(N);Nzj9Y0kE++){
  708.         bkxOPzPX = max_L(bkxOPzPX, A[Nzj9Y0kE]);
  709.       }
  710.     }
  711.     tmp =bkxOPzPX;
  712.     if(tmp <= 0){
  713.       return tmp;
  714.     }
  715.     for(i=(0);i<(N);i++){
  716.       A[i] -= i;
  717.     }
  718.     sortA_index(N, A, ind);
  719.     t.walloc(N, 1);
  720.     for(i=(0);i<(N);i++){
  721.       if(ind[i]>0){
  722.         chmax(res, tmp =t.getMaxVal(0, ind[i])+ A[i] + ind[i]);
  723.       }
  724.       else{
  725.         chmax(res, tmp =0+ A[i] + ind[i]);
  726.       }
  727.       if(tmp > 0){
  728.         t.change(ind[i], tmp);
  729.       }
  730.     }
  731.     return res;
  732.   }
  733. }
  734. ;
  735. // cLay version 20231031-1
  736.  
  737. // --- original code ---
  738. // #define main dummy_main
  739. // {}
  740. // #undef main
  741. // 
  742. // class Solution {
  743. // public:
  744. //   ll maxBalancedSubsequenceSum(VI &nums) {
  745. //     dummy_main();
  746. //     static int N, A[1d5], ind[];
  747. //     segtree_Point_Maxval<ll> t;
  748. //     ll res = 0, tmp;
  749. // 
  750. //     N = vec2arr(nums, A);
  751. //     tmp = max(A(N));
  752. //     if(tmp <= 0) return tmp;
  753. // 
  754. //     rep(i,N) A[i] -= i;
  755. //     sortA_index(N, A, ind);
  756. //     t.walloc(N, 1);
  757. // 
  758. //     rep(i,N){
  759. //       res >?= tmp = if[ind[i]>0, t.getMaxVal(0, ind[i]), 0] + A[i] + ind[i];
  760. //       if(tmp > 0) t.change(ind[i], tmp);
  761. //     }
  762. // 
  763. //     return res;
  764. //   }
  765. // };
  766.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/yWzJ7i
language:
C++ (gcc 8.3)
created:
195 days 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!