Atcoder Library Practice Contest-segment tree( J )(without lazy updates)

[abhisek_12345]

Hey guys can someone please help me finding error in my code. 12/22 testcase are getting AC and other WA and that also alternate testcases.
Although all testcases of every other rated contest are found on atcoder dropbox but i couldn’t find testcases for Atcder Library Practice contest.
I’m particularly concerned about question J segment tree.
Link for question: segment_tree_practice

Link of my submission:Abhishek’s submission
the code i wrote is this:

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) 
#define MAXN 200006


ll t[4*MAXN]; ll nn;
//==========================FOR MAX/MIN==============================//
//\/\/\/\/\--------------for min just change max fn to min---------------------/\/\/\/\/\/\/\/\==============//
//------------array a[], current vertex(v), current index ranges of segment tree tl and tr-------------------------------------//
void mx_build(ll a[], ll v, ll tl, ll tr) {
   if (tl == tr) {
       t[v] = a[tl];
   } else {
       ll tm = (tl + tr) / 2;
       mx_build(a, v*2, tl, tm);
       mx_build(a, v*2+1, tm+1, tr);
       t[v] = max(t[v*2],t[v*2+1]);
   }
}

//------------------------------query function f max-----------------------------------------//
ll maax(ll v, ll tl, ll tr, ll l, ll r) {
   if (l > r) 
       return 0;
   if (l == tl && r == tr) {
       return t[v];
   }
   ll tm = (tl + tr) / 2;
   return max(maax(v*2, tl, tm, l, min(r, tm))
          , maax(v*2+1, tm+1, tr, max(l, tm+1), r));
}

//--------------------------update fun of max-------------------------------//
void mx_update(ll v, ll tl, ll tr, ll pos, ll new_val) {
   if (tl == tr) {
       t[v] = new_val;
   } else {
       ll tm = (tl + tr) / 2;
       if (pos <= tm)
           mx_update(v*2, tl, tm, pos, new_val);
       else
           mx_update(v*2+1, tm+1, tr, pos, new_val);
       t[v] = max(t[v*2],t[v*2+1]);
   }
}

//-----------------------first number geater than equal to x----------------------------//
ll get_first(ll v, ll lv, ll rv, ll l, ll r, ll x) {
   if(lv > r || rv < l) return nn;
   if(l <= lv && rv <= r) {
       if(t[v] < x) return nn;
       while(lv != rv) {
           ll mid = lv + (rv-lv)/2;
           if(t[2*v] > x) {
               v = 2*v;
               rv = mid;
           }else {
               v = 2*v+1;
               lv = mid+1;
           }
       }
       return lv;
   }

   ll mid = lv + (rv-lv)/2;
   ll rs = get_first(2*v, lv, mid, l, r, x);
   if(rs != nn) return rs;
   return get_first(2*v+1, mid+1, rv, l ,r, x);
}

int main(){
fastio;

ll n,q; cin>>n>>q; nn=n;
ll A[n];
FOR(i,0,n){cin>>A[i];}
mx_build(A,1,0,n-1);

ll a,l,r,x; 


FOR(i,0,q){
cin>>a;
if(a==1){
cin>>r>>x;
mx_update(1,0,n-1,r-1,x);

}
else if(a==2){
cin>>l>>r;
cout<<maax(1,0,n-1,l-1,r-1)<<"\n";

}
else{
cin>>r>>x;
cout<<get_first(1,0,n-1,r-1,n-1,x)+1LL<<"\n";
}
}

return 0;}

[cmacros]

Hello.

Are you sure that you need all this code? too define form me, and also your code is bad former.

In addition, you join C and C++ together, that is a very bad choice when you are posting code where there are other programmers.

I Worked on segment tree in the last months and also I worked to improve the quality of the code in the problem solutions, take a look at the post description here

In addition, you can found quite the same problem on my Github repository that I’m debugging a little bit but it suggests the correct idea.

You can found a good segment tree implementation on this repository

For the your solution, I’m not able to read your code, sorry it is out of all the C++ guide line for me.

[abhisek_12345]

Thanks for your attention.
but i don’t understand why did you say this.
i think the code is quite readable and crisp.
if you didn’t understand a particular part of my code, you can point it out , so that i can let you know

[cmacros]

My comment is only a suggestion, not a critic, sorry about that.

I think that competitive programming code is sometimes bad format, this means that some people that are Software architect like me that usually coding code well format are not able to read this type of code.

I know that the macros are defined to be faster into write code but in my opinion, the velocity in typing is not the bottleneck, the real bottleneck, in my opinion, is thinking into reading code.

My idea of well format code is out of your code.

• What is FOR(i,0,n){cin>>A[i];} it is better that for (auto elem : A){}?

• You are missing the space here ll n,q; cin>>n>>q; nn=n;

• The following code is bad format

  if(a==1){
  cin>>r>>x;
  mx_update(1,0,n-1,r-1,x);
  }

• Do you think that maax it is a good name for a function? Max of what?

• In a lot of solution the fastio; it not needed, if you need it, you are missing something in your solution “Usualy”

• Do you think that this is a good choice? ll t[4*MAXN]; ll nn; what is t?

This is a readable implementation of Segment Tree

  /**
 * Segment tree data structure implementation
 * Copyright (C) 2020  Vincenzo Palazzo vincenzopalazzodev@gmail.com
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
 * USA.
 */

#include <vector>

namespace cpstl {
template <class T>
class SegmentTree {
 private:
  std::vector<T> &origin;
  std::vector<T> structure;

  /**
   * This function is used build the segment tree with a binary heap
   * implementation, and it use the origin array stored in the class.
   * @tparam T is the type of structure, usually it is a int or another numeric
   * type
   * @param left_index the left index of the range
   * @param right_index the right index of the range
   */
  void build_structure(int left_index, int right_index) {
    build_structure_procedure(1, left_index, right_index - 1);
  }
  /**
   * This is the sub procedure that help the build_structure procedure to make
   * the logic inside the segment tree
   * @tparam T is the type of structure, usually it is a int or another numeric
   * type
   * @param start_index
   * @param left_index
   * @param right_index
   */
  void build_structure_procedure(std::size_t start_index, std::size_t left_index,
                                 std::size_t right_index) {
    if (left_index == right_index) {
      // Leaf node will have a single element
      structure[start_index] = left_index;
      return;
    }
    auto middle_point = (left_index + right_index) / 2;
    auto left_child = left_child_index(start_index);
    auto right_child = right_child_index(start_index);
    build_structure_procedure(left_child, left_index, middle_point);
    build_structure_procedure(right_child, middle_point + 1, right_index);
    // Internal node will have the sum of both of its children
    auto segment_left = structure[left_child];
    auto segment_right = structure[right_child];
    structure[start_index] = (origin[segment_left] <= origin[segment_right])
                                 ? segment_left
                                 : segment_right;
  }

  std::size_t range_query_subroutine(std::size_t start_index, std::size_t left_index_now,
                             std::size_t right_index_now, std::size_t query_left,
                             std::size_t query_right) {
    if (query_left > right_index_now || query_right < left_index_now)
      return -1;  // outside the range
    if (left_index_now >= query_left && right_index_now <= query_right)
      return structure[start_index];  // range represented by a node is
                                      // completely inside the given range
    // range represented by a node is partially inside and partially outside the
    // given range
    auto middle_point = (left_index_now + right_index_now) / 2;
    auto left_child = left_child_index(start_index);
    auto right_child = right_child_index(start_index);
    auto left_segment = range_query_subroutine(
        left_child, left_index_now, middle_point, query_left, query_right);
    auto right_segment =
        range_query_subroutine(right_child, middle_point + 1, right_index_now,
                               query_left, query_right);
    if (left_segment == -1) return right_segment;
    if (right_segment == -1) return left_segment;
    return (origin[left_segment] <= origin[right_segment]) ? left_segment
                                                           : right_segment;
  }

  void update_subroutine(std::size_t start_index, std::size_t left_index, std::size_t right_index,
                         std::size_t pos, T new_value) {
    if (left_index == right_index) {
      origin[pos] = new_value;
      structure[start_index] = pos;
    } else {
      auto middle_point = (left_index + right_index) / 2;
      auto left_child = left_child_index(start_index);
      auto right_child = right_child_index(start_index);
      if (pos <= middle_point) {
        update_subroutine(left_child, left_index, middle_point, pos, new_value);
      } else {
        update_subroutine(right_child, middle_point + 1, right_index, pos,
                          new_value);
      }
      auto segment_left = structure[left_child];
      auto segment_right = structure[right_child];
      structure[start_index] = (origin[segment_left] <= origin[segment_right])
                                   ? segment_left
                                   : segment_right;
    }
  }

  inline std::size_t left_child_index(std::size_t const index) {
    // return index << 1;
    return index * 2;
  }

  inline std::size_t right_child_index(std::size_t const index) {
    // return (index << 1) + 1;
    return (index * 2) + 1;
  }

 public:
  SegmentTree(std::vector<T> &origin) : origin(origin) {
    auto size = origin.size();
    structure = std::vector<T>(size * 4);
    origin = origin;
    build_structure(0, size);
  }

  virtual ~SegmentTree() { structure.clear(); }

  std::size_t range_query(std::size_t start_index, std::size_t end_index) {
    return range_query_subroutine(1, 0, origin.size() - 1, start_index,
                                  end_index);
  }

  /**
   * This is the sub procedure that help the build_structure procedure to make
   * the logic inside the segment tree
   * @param at: it is the position in the original array, the function change
   * the value also in the original array
   * @param new_value the value that we want override in position at.
   */
  void update(std::size_t const at, T value) {
    update_subroutine(1, 0, origin.size() - 1, at, value);
  }

  inline T get_elem(std::size_t const at) { return origin[at]; }
};
};  // namespace cpstl

Source: GitHub - vincenzopalazzo/cpstl: Copy and Paste standard library (CPSTL) is a repository with a collection of data structure and algorithms in many different languages

[abhisek_12345]

Thank you Mr. cmacros sir.
I understand your genuine concern.
i understand as a software engineer, code with well documentation is your priority.

But since it is supposed to be just a solution of a CP platform problem , I wrote accordingly.

You’re somewhat right about fastio but we CP coders generally use it to make even more faster because best solutions(min time & space) are generally shown above than others code as you can see here in codechef.

And yes, your points are being noted. Thankyou

[cmacros]

Yes sure, it is only an opinion.

But if you think a little bit of the space solution you can not