fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxi 100000009;
  4. void build(int seg[],int low,int high,int pos,int arr[]);
  5. int query(int seg[],int qlow,int qhigh,int low,int high,int pos,int arr[]);
  6. void build(int seg[],int low,int high,int pos,int arr[])
  7. {
  8.     int mid;
  9.     if(low==high)
  10.     {
  11.          seg[pos] = arr[low];
  12.     }
  13.     else
  14.     {
  15.         mid = (low+high)/2;
  16.         build(seg,low,mid,(2*pos)+1,arr);
  17.         build(seg,mid+1,high,(2*pos)+2,arr);
  18.         seg[pos] = min(seg[(2*pos)+1],seg[(2*pos)+2]);
  19.     }
  20. }
  21.  
  22. int query(int seg[],int qlow,int qhigh,int low,int high,int pos,int arr[])
  23. {
  24.     int mid;
  25.     if(qlow<=low && qhigh>=high)
  26.     {
  27.         return seg[pos];//total overlap
  28.     }
  29.     else if(qlow>high || qhigh<low )
  30.     {
  31.         //no overlap
  32.         return 1000000;
  33.     }
  34.     else
  35.     {
  36.         mid = (low+high)/2;
  37.         return min(query(seg,qlow,qhigh,low,mid,(2*pos)+1,arr),query(seg,qlow,qhigh,mid+1,high,(2*pos)+2,arr));
  38.     }
  39. }
  40. int update(int seg[],int low,int high,int pos,int idx,int value,int arr[])
  41. {
  42.     int mid;
  43.     if(low==high)
  44.     {
  45.         seg[pos] = value;
  46.         arr[idx] = value;
  47.     }
  48.     else
  49.     {
  50.         mid = (low+high)/2;
  51.         if(idx>=low && idx<=high)
  52.         {update(seg,low,mid,(2*pos)+1,idx,value,arr);}
  53. else
  54.      {update(seg,mid+1,high,(2*pos)+2,idx,value,arr);}
  55.  
  56.  
  57.         seg[pos] = min(seg[(2*pos) +1],seg[(2*pos) +2]);
  58.     }
  59. }
  60.  
  61. int seg[2000005];
  62.  
  63. int arr[2000005];
  64. int main()
  65. {
  66.  
  67.     int a,b,c,d,e,f,g,h,i,j,k,l;
  68.     cin>>a;
  69.     cin>>b;
  70. for(c=0;c<1000000;c++)
  71.     seg[c]=100000;
  72.   for(c=0;c<a;c++)
  73.         cin>>arr[c];
  74.     build(seg,0,a-1,0,arr);
  75.  
  76.         char ch;int z;
  77.     for(c=0;c<b;c++)
  78.     {
  79.         cin>>ch>>e>>f;
  80.         if(ch=='q')
  81.         {
  82.        k =  query(seg,e-1,f-1,0,a-1,0,arr);
  83.        cout<<k<<"\n";
  84.  
  85.         }
  86.         else if(ch=='u')
  87.         {
  88. update(seg,0,a-1,0,e-1,f,arr);
  89.  
  90.         }
  91.     }
  92. }
  93.  
Success #stdin #stdout 0s 30864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Y8JSlw
language:
C++ (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!