fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MD (1000000007U)
  5. void*wmem;
  6. char memarr[96000000];
  7. template<class S, class T> inline S max_L(S a,T b){
  8.   return a>=b?a:b;
  9. }
  10. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  11.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  12.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  13.   (*arr)=(T*)(*mem);
  14.   (*mem)=((*arr)+x);
  15. }
  16. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  17.   walloc1d(arr, x2-x1, mem);
  18.   (*arr) -= x1;
  19. }
  20. template<class T> struct Arr1d{
  21.   int n;
  22.   int mem;
  23.   T*d;
  24.   T& operator[](int a){
  25.     return d[a];
  26.   }
  27.   void sort(){
  28.     reset();
  29.     std::sort(d, d+n);
  30.   }
  31.   int set_cumulative_sum;
  32.   int cumulative_sum_mem;
  33.   T*cumulative_sum;
  34.   void setSum(void){
  35.     int i;
  36.     set_cumulative_sum = 1;
  37.     if(cumulative_sum_mem < n+1){
  38.       delete[] cumulative_sum;
  39.       cumulative_sum = new T[n+1];
  40.       cumulative_sum_mem = n+1;
  41.     }
  42.     cumulative_sum[0] = 0;
  43.     for(i=(0);i<(n);i++){
  44.       cumulative_sum[i+1] = cumulative_sum[i] + d[i];
  45.     }
  46.   }
  47.   T getSum(int i, int j){
  48.     if(set_cumulative_sum==0){
  49.       setSum();
  50.     }
  51.     return cumulative_sum[j+1] - cumulative_sum[i];
  52.   }
  53.   int set_const_len_left;
  54.   int const_len_left_mem;
  55.   int*const_len_left;
  56.   void setConstLenLeft(void){
  57.     int i;
  58.     set_const_len_left = 1;
  59.     if(const_len_left_mem < n){
  60.       delete[] const_len_left;
  61.       const_len_left = new int[n];
  62.       const_len_left_mem = n;
  63.     }
  64.     for(i=(0);i<(n);i++){
  65.       const_len_left[i] = 1;
  66.     }
  67.     for(i=(1);i<(n);i++){
  68.       if(d[i]==d[i-1]){
  69.         const_len_left[i] = const_len_left[i-1] + 1;
  70.       }
  71.     }
  72.   }
  73.   int ConstLenLeft(int st, T val){
  74.     if(!set_const_len_left){
  75.       setConstLenLeft();
  76.     }
  77.     if(val != d[st]){
  78.       return 0;
  79.     }
  80.     return const_len_left[st];
  81.   }
  82.   int ConstLenLeft(int st){
  83.     if(!set_const_len_left){
  84.       setConstLenLeft();
  85.     }
  86.     return const_len_left[st];
  87.   }
  88.   int ConstLenLeftCyclic(int st, T val){
  89.     if(!set_const_len_left){
  90.       setConstLenLeft();
  91.     }
  92.     st %= n;
  93.     if(st < 0){
  94.       st += n;
  95.     }
  96.     if(val != d[st]){
  97.       return 0;
  98.     }
  99.     if(const_len_left[st] != st+1 || d[st] != d[n-1]){
  100.       return const_len_left[st];
  101.     }
  102.     if(const_len_left[n-1] == n){
  103.       return 1073709056;
  104.     }
  105.     return const_len_left[st] + const_len_left[n-1];
  106.   }
  107.   int ConstLenLeftCyclic(int st){
  108.     if(!set_const_len_left){
  109.       setConstLenLeft();
  110.     }
  111.     st %= n;
  112.     if(st < 0){
  113.       st += n;
  114.     }
  115.     if(const_len_left[st] != st+1 || d[st] != d[n-1]){
  116.       return const_len_left[st];
  117.     }
  118.     if(const_len_left[n-1] == n){
  119.       return 1073709056;
  120.     }
  121.     return const_len_left[st] + const_len_left[n-1];
  122.   }
  123.   int set_const_len_right;
  124.   int const_len_right_mem;
  125.   int*const_len_right;
  126.   void setConstLenRight(void){
  127.     int i;
  128.     set_const_len_right = 1;
  129.     if(const_len_right_mem < n){
  130.       delete[] const_len_right;
  131.       const_len_right = new int[n];
  132.       const_len_right_mem = n;
  133.     }
  134.     for(i=(0);i<(n);i++){
  135.       const_len_right[i] = 1;
  136.     }
  137.     for(i=(n-1)-1;i>=(0);i--){
  138.       if(d[i]==d[i+1]){
  139.         const_len_right[i] = const_len_right[i+1] + 1;
  140.       }
  141.     }
  142.   }
  143.   int ConstLenRight(int st, T val){
  144.     if(!set_const_len_right){
  145.       setConstLenRight();
  146.     }
  147.     if(val != d[st]){
  148.       return 0;
  149.     }
  150.     return const_len_right[st];
  151.   }
  152.   int ConstLenRight(int st){
  153.     if(!set_const_len_right){
  154.       setConstLenRight();
  155.     }
  156.     return const_len_right[st];
  157.   }
  158.   int ConstLenRightCyclic(int st, T val){
  159.     if(!set_const_len_right){
  160.       setConstLenRight();
  161.     }
  162.     if(val != d[st]){
  163.       return 0;
  164.     }
  165.     st %= n;
  166.     if(st < 0){
  167.       st += n;
  168.     }
  169.     if(const_len_right[st] != n-st || d[st] != d[0]){
  170.       return const_len_right[st];
  171.     }
  172.     if(const_len_right[0] == n){
  173.       return 1073709056;
  174.     }
  175.     return const_len_right[st] + const_len_right[0];
  176.   }
  177.   int ConstLenRightCyclic(int st){
  178.     if(!set_const_len_right){
  179.       setConstLenRight();
  180.     }
  181.     st %= n;
  182.     if(st < 0){
  183.       st += n;
  184.     }
  185.     if(const_len_right[st] != n-st || d[st] != d[0]){
  186.       return const_len_right[st];
  187.     }
  188.     if(const_len_right[0] == n){
  189.       return 1073709056;
  190.     }
  191.     return const_len_right[st] + const_len_right[0];
  192.   }
  193.   int set_dhist;
  194.   int dhist_mem;
  195.   int*dhist;
  196.   int*dhists;
  197.   T dhist_mn;
  198.   T dhist_mx;
  199.   void setDHist(void){
  200.     int i;
  201.     int len;
  202.     set_dhist = 1;
  203.     if(n==0){
  204.       return;
  205.     }
  206.     dhist_mn = dhist_mx = d[0];
  207.     for(i=(1);i<(n);i++){
  208.       if(dhist_mn > d[i]){
  209.         dhist_mn = d[i];
  210.       }
  211.       if(dhist_mx < d[i]){
  212.         dhist_mx = d[i];
  213.       }
  214.     }
  215.     len = dhist_mx - dhist_mn + 1;
  216.     if(dhist_mem < len){
  217.       delete[] dhist;
  218.       dhist = new int[len];
  219.       delete[] dhists;
  220.       dhists = new int[len+1];
  221.       dhist_mem = len;
  222.     }
  223.     for(i=(0);i<(len);i++){
  224.       dhist[i] = 0;
  225.     }
  226.     for(i=(0);i<(n);i++){
  227.       dhist[d[i] - dhist_mn]++;
  228.     }
  229.     dhists[0] = 0;
  230.     for(i=(0);i<(len);i++){
  231.       dhists[i+1] = dhists[i] + dhist[i];
  232.     }
  233.   }
  234.   int dHist(T x){
  235.     if(set_dhist==0){
  236.       setDHist();
  237.     }
  238.     if(n == 0 || x < dhist_mn || x > dhist_mx){
  239.       return 0;
  240.     }
  241.     return dhist[x - dhist_mn];
  242.   }
  243.   int dHist(T x, T y){
  244.     if(set_dhist==0){
  245.       setDHist();
  246.     }
  247.     if(x < dhist_mn){
  248.       x = dhist_mn;
  249.     }
  250.     if(y > dhist_mx){
  251.       y = dhist_mx;
  252.     }
  253.     if(n == 0 || x > y){
  254.       return 0;
  255.     }
  256.     return dhists[y-dhist_mn+1] - dhists[x-dhist_mn];
  257.   }
  258.   int set_shist;
  259.   int shist_mem;
  260.   T*shist;
  261.   void setSHist(void){
  262.     int i;
  263.     set_shist = 1;
  264.     if(shist_mem < n){
  265.       delete[] shist;
  266.       shist = new T[n];
  267.       shist_mem = n;
  268.     }
  269.     for(i=(0);i<(n);i++){
  270.       shist[i] = d[i];
  271.     }
  272.     std::sort(shist, shist + n);
  273.   }
  274.   int sHist(T x){
  275.     if(set_shist==0){
  276.       setSHist();
  277.     }
  278.     auto r = equal_range(shist, shist+n, x);
  279.     return r.second - r.first;
  280.   }
  281.   int sHist(T x, T y){
  282.     if(set_shist==0){
  283.       setSHist();
  284.     }
  285.     return upper_bound(shist, shist+n, y) - lower_bound(shist, shist+n, x);
  286.   }
  287.   int set_prevLE;
  288.   int prevLE_mem;
  289.   int*prevLE;
  290.   int setPrevLE(void *mem = wmem){
  291.     int i;
  292.     int s = 0;
  293.     int*st;
  294.     set_prevLE = 1;
  295.     if(prevLE_mem < n){
  296.       delete[] prevLE;
  297.       prevLE = new int[n];
  298.       prevLE_mem = n;
  299.     }
  300.     walloc1d(&st, n, &mem);
  301.     for(i=(0);i<(n);i++){
  302.       while(s && d[st[s-1]] > d[i]){
  303.         s--;
  304.       }
  305.       if(s==0){
  306.         prevLE[i] = -1;
  307.       }
  308.       else{
  309.         prevLE[i] = st[s-1];
  310.       }
  311.       st[s++] = i;
  312.     }
  313.   }
  314.   int PrevLE(int i){
  315.     if(set_prevLE==0){
  316.       setPrevLE();
  317.     }
  318.     return prevLE[i];
  319.   }
  320.   int set_prevLT;
  321.   int prevLT_mem;
  322.   int*prevLT;
  323.   int setPrevLT(void *mem = wmem){
  324.     int i;
  325.     int s = 0;
  326.     int*st;
  327.     set_prevLT = 1;
  328.     if(prevLT_mem < n){
  329.       delete[] prevLT;
  330.       prevLT = new int[n];
  331.       prevLT_mem = n;
  332.     }
  333.     walloc1d(&st, n, &mem);
  334.     for(i=(0);i<(n);i++){
  335.       while(s && d[st[s-1]] >= d[i]){
  336.         s--;
  337.       }
  338.       if(s==0){
  339.         prevLT[i] = -1;
  340.       }
  341.       else{
  342.         prevLT[i] = st[s-1];
  343.       }
  344.       st[s++] = i;
  345.     }
  346.   }
  347.   int PrevLT(int i){
  348.     if(set_prevLT==0){
  349.       setPrevLT();
  350.     }
  351.     return prevLT[i];
  352.   }
  353.   int set_prevGE;
  354.   int prevGE_mem;
  355.   int*prevGE;
  356.   int setPrevGE(void *mem = wmem){
  357.     int i;
  358.     int s = 0;
  359.     int*st;
  360.     set_prevGE = 1;
  361.     if(prevGE_mem < n){
  362.       delete[] prevGE;
  363.       prevGE = new int[n];
  364.       prevGE_mem = n;
  365.     }
  366.     walloc1d(&st, n, &mem);
  367.     for(i=(0);i<(n);i++){
  368.       while(s && d[st[s-1]] < d[i]){
  369.         s--;
  370.       }
  371.       if(s==0){
  372.         prevGE[i] = -1;
  373.       }
  374.       else{
  375.         prevGE[i] = st[s-1];
  376.       }
  377.       st[s++] = i;
  378.     }
  379.   }
  380.   int PrevGE(int i){
  381.     if(set_prevGE==0){
  382.       setPrevGE();
  383.     }
  384.     return prevGE[i];
  385.   }
  386.   int set_prevGT;
  387.   int prevGT_mem;
  388.   int*prevGT;
  389.   int setPrevGT(void *mem = wmem){
  390.     int i;
  391.     int s = 0;
  392.     int*st;
  393.     set_prevGT = 1;
  394.     if(prevGT_mem < n){
  395.       delete[] prevGT;
  396.       prevGT = new int[n];
  397.       prevGT_mem = n;
  398.     }
  399.     walloc1d(&st, n, &mem);
  400.     for(i=(0);i<(n);i++){
  401.       while(s && d[st[s-1]] <= d[i]){
  402.         s--;
  403.       }
  404.       if(s==0){
  405.         prevGT[i] = -1;
  406.       }
  407.       else{
  408.         prevGT[i] = st[s-1];
  409.       }
  410.       st[s++] = i;
  411.     }
  412.   }
  413.   int PrevGT(int i){
  414.     if(set_prevGT==0){
  415.       setPrevGT();
  416.     }
  417.     return prevGT[i];
  418.   }
  419.   int set_nextLE;
  420.   int nextLE_mem;
  421.   int*nextLE;
  422.   int setNextLE(void *mem = wmem){
  423.     int i;
  424.     int s = 0;
  425.     int*st;
  426.     set_nextLE = 1;
  427.     if(nextLE_mem < n){
  428.       delete[] nextLE;
  429.       nextLE = new int[n];
  430.       nextLE_mem = n;
  431.     }
  432.     walloc1d(&st, n, &mem);
  433.     for(i=(n)-1;i>=(0);i--){
  434.       while(s && d[st[s-1]] > d[i]){
  435.         s--;
  436.       }
  437.       if(s==0){
  438.         nextLE[i] = n;
  439.       }
  440.       else{
  441.         nextLE[i] = st[s-1];
  442.       }
  443.       st[s++] = i;
  444.     }
  445.   }
  446.   int NextLE(int i){
  447.     if(set_nextLE==0){
  448.       setNextLE();
  449.     }
  450.     return nextLE[i];
  451.   }
  452.   int set_nextLT;
  453.   int nextLT_mem;
  454.   int*nextLT;
  455.   int setNextLT(void *mem = wmem){
  456.     int i;
  457.     int s = 0;
  458.     int*st;
  459.     set_nextLT = 1;
  460.     if(nextLT_mem < n){
  461.       delete[] nextLT;
  462.       nextLT = new int[n];
  463.       nextLT_mem = n;
  464.     }
  465.     walloc1d(&st, n, &mem);
  466.     for(i=(n)-1;i>=(0);i--){
  467.       while(s && d[st[s-1]] >= d[i]){
  468.         s--;
  469.       }
  470.       if(s==0){
  471.         nextLT[i] = n;
  472.       }
  473.       else{
  474.         nextLT[i] = st[s-1];
  475.       }
  476.       st[s++] = i;
  477.     }
  478.   }
  479.   int NextLT(int i){
  480.     if(set_nextLT==0){
  481.       setNextLT();
  482.     }
  483.     return nextLT[i];
  484.   }
  485.   int set_nextGE;
  486.   int nextGE_mem;
  487.   int*nextGE;
  488.   int setNextGE(void *mem = wmem){
  489.     int i;
  490.     int s = 0;
  491.     int*st;
  492.     set_nextGE = 1;
  493.     if(nextGE_mem < n){
  494.       delete[] nextGE;
  495.       nextGE = new int[n];
  496.       nextGE_mem = n;
  497.     }
  498.     walloc1d(&st, n, &mem);
  499.     for(i=(n)-1;i>=(0);i--){
  500.       while(s && d[st[s-1]] < d[i]){
  501.         s--;
  502.       }
  503.       if(s==0){
  504.         nextGE[i] = n;
  505.       }
  506.       else{
  507.         nextGE[i] = st[s-1];
  508.       }
  509.       st[s++] = i;
  510.     }
  511.   }
  512.   int NextGE(int i){
  513.     if(set_nextGE==0){
  514.       setNextGE();
  515.     }
  516.     return nextGE[i];
  517.   }
  518.   int set_nextGT;
  519.   int nextGT_mem;
  520.   int*nextGT;
  521.   int setNextGT(void *mem = wmem){
  522.     int i;
  523.     int s = 0;
  524.     int*st;
  525.     set_nextGT = 1;
  526.     if(nextGT_mem < n){
  527.       delete[] nextGT;
  528.       nextGT = new int[n];
  529.       nextGT_mem = n;
  530.     }
  531.     walloc1d(&st, n, &mem);
  532.     for(i=(n)-1;i>=(0);i--){
  533.       while(s && d[st[s-1]] <= d[i]){
  534.         s--;
  535.       }
  536.       if(s==0){
  537.         nextGT[i] = n;
  538.       }
  539.       else{
  540.         nextGT[i] = st[s-1];
  541.       }
  542.       st[s++] = i;
  543.     }
  544.   }
  545.   int NextGT(int i){
  546.     if(set_nextGT==0){
  547.       setNextGT();
  548.     }
  549.     return nextGT[i];
  550.   }
  551.   void reset(){
  552.     set_cumulative_sum = 0;
  553.     set_const_len_left = 0;
  554.     set_const_len_right = 0;
  555.     set_dhist = 0;
  556.     set_prevLE = set_prevLT = set_prevGE = set_prevGT = 0;
  557.     set_nextLE = set_nextLT = set_nextGE = set_nextGT = 0;
  558.   }
  559.   void memory_expand(int nn){
  560.     if(mem < nn){
  561.       delete[] d;
  562.       d = new T[nn];
  563.       mem = nn;
  564.     }
  565.   }
  566.   void malloc(int nn){
  567.     reset();
  568.     memory_expand(nn);
  569.     n = nn;
  570.   }
  571.   void setN(int nn){
  572.     reset();
  573.     memory_expand(nn);
  574.     n = nn;
  575.   }
  576.   void set(vector<T> &a){
  577.     int i;
  578.     int nn = a.size();
  579.     setN(nn);
  580.     for(i=(0);i<(nn);i++){
  581.       d[i] = a[i];
  582.     }
  583.   }
  584.   void set(int nn, T a[]){
  585.     int i;
  586.     setN(nn);
  587.     for(i=(0);i<(nn);i++){
  588.       d[i] = a[i];
  589.     }
  590.   }
  591.   void free(){
  592.     destructor();
  593.   }
  594.   void constructor(){
  595.     n = mem = 0;
  596.     d = NULL;
  597.     set_cumulative_sum = 0;
  598.     cumulative_sum_mem = 0;
  599.     cumulative_sum = NULL;
  600.     set_const_len_left = 0;
  601.     const_len_left_mem = 0;
  602.     const_len_left = NULL;
  603.     set_const_len_right = 0;
  604.     const_len_right_mem = 0;
  605.     const_len_right = NULL;
  606.     set_dhist = 0;
  607.     dhist_mem = 0;
  608.     dhist = NULL;
  609.     dhists = NULL;
  610.     set_shist = 0;
  611.     shist_mem = 0;
  612.     shist = NULL;
  613.     set_prevLE = set_prevLT = set_prevGE = set_prevGT = 0;
  614.     prevLE_mem = prevLT_mem = prevGE_mem = prevGT_mem = 0;
  615.     prevLE = prevLT = prevGE = prevGT = NULL;
  616.     set_nextLE = set_nextLT = set_nextGE = set_nextGT = 0;
  617.     nextLE_mem = nextLT_mem = nextGE_mem = nextGT_mem = 0;
  618.     nextLE = nextLT = nextGE = nextGT = NULL;
  619.   }
  620.   void constructor(int nn){
  621.     constructor();
  622.     malloc(nn);
  623.   }
  624.   void destructor(){
  625.     delete[] d;
  626.     d = NULL;
  627.     mem = n = 0;
  628.     set_cumulative_sum = 0;
  629.     cumulative_sum_mem = 0;
  630.     delete[] cumulative_sum;
  631.     cumulative_sum = NULL;
  632.     set_const_len_left = 0;
  633.     const_len_left_mem = 0;
  634.     delete[] const_len_left;
  635.     const_len_left = NULL;
  636.     set_const_len_right = 0;
  637.     const_len_right_mem = 0;
  638.     delete[] const_len_right;
  639.     const_len_right = NULL;
  640.     set_dhist = 0;
  641.     dhist_mem = 0;
  642.     delete[] dhist;
  643.     delete[] dhists;
  644.     dhist = NULL;
  645.     set_shist = 0;
  646.     shist_mem = 0;
  647.     delete[] shist;
  648.     shist = NULL;
  649.     set_prevLE = set_prevLT = set_prevGE = set_prevGT = 0;
  650.     prevLE_mem = prevLT_mem = prevGE_mem = prevGT_mem = 0;
  651.     delete[] prevLE;
  652.     delete[] prevLT;
  653.     delete[] prevGE;
  654.     delete[] prevGT;
  655.     prevLE = prevLT = prevGE = prevGT = NULL;
  656.     set_nextLE = set_nextLT = set_nextGE = set_nextGT = 0;
  657.     nextLE_mem = nextLT_mem = nextGE_mem = nextGT_mem = 0;
  658.     delete[] nextLE;
  659.     delete[] nextLT;
  660.     delete[] nextGE;
  661.     delete[] nextGT;
  662.     nextLE = nextLT = nextGE = nextGT = NULL;
  663.   }
  664.   Arr1d(){
  665.     constructor();
  666.   }
  667.   Arr1d(int nn){
  668.     constructor(nn);
  669.   }
  670.   ~Arr1d(){
  671.     destructor();
  672.   }
  673. }
  674. ;
  675. #define main dummy_main
  676. int main(){
  677.   wmem = memarr;
  678.   return 0;
  679. }
  680. #undef main
  681. Arr1d<int> A;
  682. class Solution{
  683.   public:
  684.   int waysToSplit(vector<int>& nums){
  685.     int i;
  686.     int N = nums.size();
  687.     int x = 1;
  688.     int y = 1;
  689.     long long res = 0;
  690.     A.set(nums);
  691.     for(i=(1);i<(N-1);i++){
  692.       while(x < N-i && A.getSum(0,i-1) > A.getSum(i,i+x-1)){
  693.         x++;
  694.       }
  695.       while(y < N-i && A.getSum(i,i+y-1) <= A.getSum(i+y,N-1)){
  696.         y++;
  697.       }
  698.       if(y > x){
  699.         res += y - x;
  700.       }
  701.       x =max_L(1, x-1);
  702.       y =max_L(1, y-1);
  703.     }
  704.     return res % MD;
  705.   }
  706. }
  707. ;
  708. // cLay version 20210103-1
  709.  
  710. // --- original code ---
  711. // #define main dummy_main
  712. // {}
  713. // #undef main
  714. // 
  715. // Arr1d<int> A;
  716. // 
  717. // class Solution {
  718. // public:
  719. //   int waysToSplit(vector<int>& nums) {
  720. //     int N = nums.size(), x = 1, y = 1;
  721. //     ll res = 0;
  722. //     
  723. //     A.set(nums);
  724. //     rep(i,1,N-1){
  725. //       while(x < N-i && A.getSum(0,i-1) > A.getSum(i,i+x-1)) x++;
  726. //       while(y < N-i && A.getSum(i,i+y-1) <= A.getSum(i+y,N-1)) y++;
  727. //       if(y > x) res += y - x;
  728. //       x = max(1, x-1);
  729. //       y = max(1, y-1);
  730. //     }
  731. // 
  732. //     return res % MD;
  733. //   }
  734. // };
  735.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/tc420w
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!