By Muhammad_mhs, history, 8 months ago,
Please! Can anyone tell me in which case my solution is being WA?


My Solution: 132257155

• -20

By Muhammad_mhs, history, 11 months ago,

I got this(ADATREE — Ada and Trees) problem from morass blog segment tree section. I stuck to analyzing the both time complexity and memory complexity of this problem in the worst case for this AC solution.

My Solution:

///   BISMILLAHIR RAHMANIR RAHEEM
#include<bits/stdc++.h>
using namespace std;
#define all(x)          (x).begin(), (x).end()
using ll = long long;
const ll N = 3e5 + 5;

vector < ll > tr[N<<2];

ll n;
ll arr[N];
ll q;
ll x;

vector < ll >  merge( vector<ll> a , vector<ll> b ){

vector<ll> order;
while( a.size() and b.size() ){
int x = a.back();
int y = b.back();
if ( x <= y ) {
order.push_back ( x );
a.pop_back();
}
else {
order.push_back ( y );
b.pop_back();
}
}

while(a.size()) order.push_back(a.back()) , a.pop_back();
while(b.size()) order.push_back(b.back()) , b.pop_back();
return order;
}

void build(ll u, ll st, ll en) {

if (st==en) {
tr[u].push_back ( arr[st] );
}
else {
ll mid = (st+en)/2;
build(2*u, st, mid);
build(2*u+1, mid+1, en);

vector < ll > bame = tr[2*u];
vector < ll > dane = tr[2*u+1];
reverse ( all ( bame ) );
reverse ( all ( dane ) );

vector<ll> res = merge( bame , dane );
reverse ( all ( res ) );
while(res.size()){
tr[u].push_back ( res.back() );
res.pop_back();
}
}
}

ll query(ll u, ll st, ll en, ll l, ll r) {

ll bame , dane , res;
if (r<st || en<l)  return 0;
if (l<=st && en<=r){
ll lo = st;
ll hi = en;
ll mx = 0;
while(lo<=hi){
ll mid = (lo+hi)>>1;
ll cur = tr[u][mid-st];
if ( cur > x ) hi = mid - 1;
else{
lo = mid + 1;
mx = max ( mx , cur );
}
}
return mx;
}
ll mid = (st+en)/2;
bame = query(2*u, st, mid, l, r);
dane = query(2*u+1, mid+1, en, l, r);

return max(bame,dane);
}

void Solution ( int tc ){

cin >> n >> q;
for ( int i = 1 ; i <= n ; ++i ) cin >> arr[i];
build ( 1 , 1 , n );
for ( int i = 1 ; i <= q ; i++ ){
ll l , r;
cin >> l >> r >> x;
l++;
r++;
ll res = query ( 1 , 1 , n , l , r );
cout << res << "\n";
}
return;
}

int main()
{

int testcase = 1 , tc = 0;

/// cin >> testcase;

for ( int i = 1 ; i <= testcase ; ++i ){
Solution( ++tc );
}
return 0;
}

/*

Explanation:

Time :

----------------------------------------------------------------------------------------------------------------

Alhamdulillah
*/



Can anyone help me to calculate this. Thanks in advance.

• 0

By Muhammad_mhs, history, 11 months ago,

My approach to solving this problem was the segment tree with O(n(logn)^2) complexity. but It gives me TLE.

My Submission: 124635301

Please, anyone, help me why this solution gives me TLE

• +3

By Muhammad_mhs, history, 15 months ago,

This problem from timus , For this problem, I got AC by this solution. The solution is not working in my codeblocks IDE, but when I reduce the constraints then it works in my CodeBlocks IDE. Currently I have Used codeblocks 20.03 version. Can anyone please help me ? Thanks in advance.

• +9

By Muhammad_mhs, history, 21 month(s) ago,

Stick Lengths In this problem , sort the array and I have to make all sticks size equal to array[n/2] ( n/2 = median ) then answer should be the minimum. But why I choose median index. Can anyone explain, Please ? Thanks in advance.

• 0

By Muhammad_mhs, history, 2 years ago,

In this problem, I have to find sum of all pairs lcm of an array. I find this from morass blog.Can anyone explain it. Thanks in advance.

• 0

By Muhammad_mhs, history, 2 years ago,

In this problem the number of integer points on a segment is gcd(x,y)+1. where x = abs(x1-x2) and y = abs(y1-y2). But why it does? Anyone please explain it. Thanks in advance.

• +3

By Muhammad_mhs, history, 2 years ago,

How can I solve 20 digit number factorization ? Problem link Can anyone explain,please?

• 0

By Muhammad_mhs, history, 2 years ago,

How to find Lexicographical smallest longest common subsequence ??

• 0

By Muhammad_mhs, history, 3 years ago,

Can anyone help me for this problem?link is here. I get it from there