fork download
copy 
  1. #include <fstream>
  2. #include <math.h>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. ifstream fin("vao.inp");
  8. ofstream fout("ra.out");
  9.  
  10. const int maxN = 1e5;
  11. const int maxT = 4*maxN;
  12. const int minint = -2e9;
  13.  
  14. class Interval_tree
  15. {
  16. public:
  17.     /* properties */
  18.     int depth, numL, firstB;
  19.     int T[maxT];
  20.     int startI[maxT], endI[maxT];
  21.     /* method */
  22.     void init(int *a, int n);
  23.     int get_max(int left, int right);
  24.     void fix(int i, int v);
  25. };
  26.  
  27. void Interval_tree::init(int *a, int n)
  28. {
  29.     for(depth=0;(1<<depth)<n;depth++);
  30.     numL =1<<depth;
  31.     firstB = numL-1;
  32.     for(int i=0;i<n;i++)
  33.     {
  34.         T[firstB+i] = a[i];
  35.         startI[firstB+i] = i;
  36.         endI[firstB+i] = i;
  37.     }
  38.     for(int i=firstB-1;i>-1;i--)
  39.     {
  40.         T[i] = max(T[(i<<1)+1],T[(i<<1)+2]);
  41.         startI[i] = min(startI[(i<<1)+1],startI[(i<<1)+2]);
  42.         endI[i] = max(endI[(i<<1)+2],endI[(i<<1)+1]);
  43.     }
  44.     return;
  45. }
  46.  
  47. int Interval_tree::get_max(int left, int right)
  48. {
  49.     int i, res=minint;
  50.     std::vector <int> stackI;
  51.     stackI.push_back(0);
  52.     while(!stackI.empty())
  53.     {
  54.         i = stackI.back();
  55.         stackI.pop_back();
  56.         if(left>endI[i] || right<startI[i]) continue;
  57.         if(left<=startI[i] && right>=endI[i])
  58.         {
  59.             res=max(res,T[i]);
  60.             continue;
  61.         }
  62.         stackI.push_back((i<<1)+1);
  63.         stackI.push_back((i<<1)+2);
  64.     }
  65.     return res;
  66. }
  67.  
  68. void Interval_tree::fix(int i, int v)
  69. {
  70.     int j = firstB+i;
  71.     T[j]=v;
  72.     for(--j>>1;j>=0;--j>>1) T[j]= max(T[(j<<1)+1],T[(i<<1)+2]);
  73.     return;
  74. }
  75.  
  76. int a[maxN];
  77.  
  78. int n,m,kind,L,R,v;
  79.  
  80. Interval_tree Ia;
  81.  
  82. int main()
  83. {
  84.     fin >> n >> m;
  85.     for(int i=0;i<n;i++) fin >> a[i];
  86.     Ia.init(a,n);
  87.     for(int i=0;i<m;i++)
  88.     {
  89.         fin >> kind >> L >> R;
  90.         if (kind==1) { a[L]=R; Ia.fix(L-1,R); }
  91.         if (kind==2) fout << Ia.get_max(L-1,R-1)<<endl;
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 8504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3djQsA
language:
C++ (gcc 8.3)
created:
10 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!