I am getting TLE on test case 54 in segment Tree 1 Step 2 problem 4.
Problem Name → First Element at least X-2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define back(i,a,b) for(ll i =a;i>=b;i--)
ll pw(ll a, ll b) { ll g = 1; rep(i, 1, b) g *= a; return g;}
#define all(x) x.begin(),x.end()
bool comp(ll a, ll b) {
//for condition that has to true we have to return 1 and for condition that has to followed
//false we have to return 0;
if (a > b)
return 1;
return 0;
}
void print(vi v) {
for (auto f : v)
cout << f << " ";
}
vector<ll> seg(400004);
ll ar[100001];
void build(ll si , ll l , ll r) {
if (l == r) {
seg[si] = ar[l];
return;
}
ll mid = l + r;
mid /= 2;
build(2 * si + 1 , l, mid);
build(2 * si + 2, mid + 1, r);
seg[si] = max(seg[2 * si + 1], seg[2 * si + 2]);
}
// use endl in interactive problems
void update (ll si , ll l , ll r, ll k, ll val) {
if (l == r) {
ar[l] = val;
seg[si] = val;
// seg[si] = {ar[l], ar[l], ar[l], ar[l]};
return;
}
ll mid = l + r;
mid /= 2;
if (k <= mid) {
update(2 * si + 1, l , mid, k, val);
}
else
{
update(2 * si + 2, mid + 1, r, k , val);
}
seg[si] = max(seg[2 * si + 1], seg[2 * si + 2]);
}
ll ind = 1e14;
ll find(ll si , ll l , ll r, ll c, ll x) {
//cout << l << " " << r << "\n";
if (seg[si] < x || r < c ) {
// cout << l << " " << r << " " << seg[si] << " " << c << "\n";
return ind;
}
if (l == r) {
if (l >= c)
return l;
else
return ind;
}
ll mid = l + r;
mid /= 2;
return min( find(2 * si + 1, l, mid, c, x), find(2 * si + 2, mid + 1, r, c, x));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m;
cin >> n >> m;
rep(i, 1, n)
cin >> ar[i];
build(1, 1, n);
// cout << seg[3] << "\n";
while (m--) {
ll a, b, c;
cin >> a >> b >> c ;
if (a == 1) {
b++;
update(1, 1, n, b, c);
}
else
{
c++;
ll k = find(1, 1, n, c, b);
if (k == ind) {
cout << -1 << "\n";
}
else
cout << k - 1 << "\n";
}
}
}