fork(1) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define mx 100050
  6.  
  7. struct Node
  8. {
  9.     int lm , lmo , rm , rmo , mxv , mxo;
  10.     Node(){}
  11.     Node(int a , int b , int c , int d , int e , int f)
  12.     {
  13.         lm = a; lmo = b; rm = c; rmo = d; mxv = e; mxo = f;
  14.     }
  15. };
  16.  
  17. int a[mx];
  18. Node tree[3*mx];
  19.  
  20. void make_tree(int s , int e , int p)
  21. {
  22.     if(s == e)
  23.     {
  24.         tree[p] = Node(a[s],1,a[s],1,a[s],1);
  25.         return;
  26.     }
  27.     int l , r , m =(s+e)/2;
  28.     l = r = 2*p + 1;
  29.     r++;
  30.     make_tree(s,m,l);
  31.     make_tree(m+1,e,r);
  32.  
  33.     if(tree[l].rm == tree[r].lm)
  34.     {
  35.         int a , b , c , d , e;
  36.         if(tree[l].lm == tree[r].lm)
  37.         {
  38.             tree[p].lm = tree[l].lm;
  39.             tree[p].lmo = tree[l].lmo + tree[r].lmo;
  40.         }
  41.         else
  42.         {
  43.             tree[p].lm = tree[l].lm;
  44.             tree[p].lmo = tree[l].lmo;
  45.         }
  46.         if(tree[l].rm == tree[r].rm)
  47.         {
  48.             tree[p].rm = tree[r].rm;
  49.             tree[p].rmo = tree[l].rmo + tree[r].rmo;
  50.         }
  51.         else
  52.         {
  53.             tree[p].rm = tree[r].rm;
  54.             tree[p].rmo = tree[r].rmo;
  55.         }
  56.         if(tree[l].mxo > tree[r].mxo)
  57.         {
  58.             a = tree[l].mxo;
  59.             b = tree[l].mxv;
  60.         }
  61.         else
  62.         {
  63.             a = tree[r].mxo;
  64.             b = tree[r].mxv;
  65.         }
  66.         c = tree[l].rmo + tree[r].lmo;
  67.         d = tree[l].rm;
  68.  
  69.         if(a > c)
  70.         {
  71.             tree[p].mxo = a;
  72.             tree[p].mxv = b;
  73.         }
  74.         else
  75.         {
  76.             tree[p].mxo = c;
  77.             tree[p].mxv = d;
  78.         }
  79.  
  80.     }
  81.     else
  82.     {
  83.         tree[p].lm = tree[l].lm;
  84.         tree[p].lmo = tree[l].lmo;
  85.         tree[p].rm = tree[r].rm;
  86.         tree[p].rmo = tree[r].rmo;
  87.         int a , b;
  88.         if(tree[l].mxo > tree[r].mxo)
  89.         {
  90.             tree[p].mxo = tree[l].mxo;
  91.             tree[p].mxv = tree[l].mxv;
  92.         }
  93.         else
  94.         {
  95.             tree[p].mxo = tree[r].mxo;
  96.             tree[p].mxv = tree[r].mxv;
  97.         }
  98.     }
  99. }
  100. int query(int l , int r , int s , int e , int pos)
  101. {
  102.     if(s >= l && e <= r)
  103.     {
  104.         return tree[pos].mxo;
  105.     }
  106.     if(s > r || e < l)
  107.     {
  108.         return 0;
  109.     }
  110.     int left , right , mid , ans1 , ans2;
  111.     mid = (s+e)/2;
  112.     left = right = 2*pos + 1;
  113.     right++;
  114.     ans1 = query(l,r,s,mid,left);
  115.     ans2 = query(l,r,mid+1,e,right);
  116.  
  117.     if(ans1 == 0)
  118.     {
  119.         return ans2;
  120.     }
  121.     if(ans2 == 0)
  122.     {
  123.         return ans1;
  124.     }
  125.     bool a , b , c , d;
  126.     a = b = c = d = false;
  127.     if(tree[left].rmo >= ans1)
  128.     {
  129.         a = true;
  130.     }
  131.     else if(tree[left].rmo <= ans1)
  132.     {
  133.         c = true;
  134.     }
  135.     if(tree[right].lmo >= ans2)
  136.     {
  137.         b = true;
  138.     }
  139.     else if(tree[right].lmo <= ans2)
  140.     {
  141.         d = true;
  142.     }
  143.     //cout << left <<"  " << right << "  \n" << tree[left].rmo <<"  " << ans1 <<"    " << tree[right].lmo <<"  " << ans2 << endl;
  144.     int ans3 = 0 , ans4 = 0;
  145.     if(tree[left].rm == tree[right].lm)
  146.     {
  147.        if(a == true && b == true)
  148.        {
  149.             return ans1+ans2;
  150.        }
  151.        if(c == true)
  152.        {
  153.             ans3 = tree[left].rmo + ans2;
  154.        }
  155.        if(d == true)
  156.        {
  157.             ans4 = tree[right].lmo + ans1;
  158.        }
  159.     }
  160.     int x , y;
  161.     x =  max(ans1,ans2);
  162.     y = max(ans3,ans4);
  163.     return max(x,y);
  164.  
  165. }
  166. int main()
  167. {
  168.     int n;
  169.     while(scanf("%d",&n) && n != 0)
  170.     {
  171.         int i , j , k , m , q , u , v , ans;
  172.         scanf("%d",&q);
  173.         for(i = 1 ; i <= n ; i++)
  174.         {
  175.             scanf("%d",a+i);
  176.         }
  177.         make_tree(1,n,0);
  178.         for(i = 0 ; i < q ; i++)
  179.         {
  180.             scanf("%d %d",&u,&v);
  181.             ans = query(u,v,1,n,0);
  182.             printf("%d\n",ans);
  183.         }
  184.     }
  185.     return 0;
  186. }
  187.  
Time limit exceeded #stdin #stdout 5s 2587648KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KetcZR
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!