Muhammad_mhs's blog

By Muhammad_mhs, history, 3 years ago, In English
Please! Can anyone tell me in which case my solution is being WA?

My Solution: 132257155

Thanks in advance.

Full text and comments »

  • Vote: I like it
  • -20
  • Vote: I do not like it

By Muhammad_mhs, history, 3 years ago, In English

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 MUHAMMAD        ios::sync_with_stdio(0);cin.tie(0);
#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()
{
   MUHAMMAD;

   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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Muhammad_mhs, history, 3 years ago, In English

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

Thanks in advance.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By Muhammad_mhs, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

By Muhammad_mhs, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Muhammad_mhs, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Muhammad_mhs, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By Muhammad_mhs, history, 5 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Muhammad_mhs, history, 5 years ago, In English

How to find Lexicographical smallest longest common subsequence ??

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Muhammad_mhs, history, 5 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it