fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. ll l,r;
  5. ll segtree[400001];
  6. ll a[100001];
  7. ll b[100001];
  8. void build(ll node,ll b1,ll e)
  9.  
  10. {if(b1==e)
  11. {
  12.     segtree[node]=b[b1];
  13. cout<<b[b1]<<"\n";
  14. }
  15. else
  16. {
  17.     ll mid=(b1+e)/2;
  18.  
  19.   build(2*node,b1,mid);
  20.   build(2*node+1,mid+1,e);
  21.  
  22.  
  23.   l=segtree[2*node];
  24.   r=segtree[2*node+1];
  25.  
  26.   if(a[l]<a[r])
  27.   {
  28.       segtree[node]=l;
  29.  
  30.   }
  31.   else if(a[l]>a[r])
  32.   {
  33.  
  34.       segtree[node]=r;
  35.  
  36.   }
  37.   else if(a[l]==a[r])
  38.   {
  39.  
  40.       segtree[node]=l;
  41.   }
  42.   else
  43.   {
  44.  
  45.   }
  46.  
  47. }
  48.  
  49.  
  50.  
  51. }
  52. ll sum1(ll node,ll b1,ll e,ll L,ll R)
  53. {
  54.  
  55.   if(b1>R || e<L)
  56.   {
  57.             return -1;
  58.   }
  59.  
  60.   if (b1>=L && e<=R)
  61.   {
  62.             return segtree[node];  
  63.  
  64.   }
  65.  
  66.  
  67. ll mid=(b1+e)/2;
  68.  
  69. ll left=sum1(2*node,b1,mid,L,R);
  70. ll right=sum1(2*node+1,mid+1,e,L,R);
  71. if(left==-1)
  72. {
  73.     return right;
  74. }
  75. else if(right==-1)
  76. {
  77.     return left;
  78. }
  79. else
  80. {
  81.  
  82.     if(a[left]>a[right])
  83.     {
  84.             return right;
  85.     }
  86.     else
  87.     {
  88.         return left;
  89.     }
  90.  
  91.  
  92. }
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101. }
  102.  
  103. int main()
  104. {
  105.     ll n;
  106.     cin>>n;
  107.     ll i=1;
  108.     while(i<=n)
  109.     {
  110.         cin>>a[i];
  111.         b[i]=i;
  112.         i++;
  113.     }
  114.  
  115.     build(1,1,n);
  116.  
  117.  
  118.  
  119.     cout<<sum1(1,1,n,2,8);
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.     return 0;
  129. }
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
Success #stdin #stdout 0s 19920KB
comments (?)
stdin
copy 
9
1 1 2 2 3 2 1 2 1
stdout
copy 
1
2
3
4
5
6
7
8
9
2
https://ideone.com/0zzisK
language:
C++14 (gcc 8.3)
created:
4 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!