Hi I am facing an issue in the problem 2036F - XORificator 3000 where I was getting WA when I am using long long But when I looked at the editorial the only major diff was using uint64_t instead and I got accepted

Can anyone explain why this is happening given below are the 2 codes

291907844

291907876

In the last contest(Codeforces Round 976 (Div. 2)) E question I was up solving it and I was getting multiple TLEs and I saw a very similar code getting accepted The only difference was I was using my function for mod_mul instead of directly computing it in that line itself, I like to use those mod_mul,mod_add for better code readability

But in this question using those affected the verdict was it a one time thing or is it not advisable to use those functions how much difference does it actually take.

P.S Pasting both TLEd and Accepted solution for reference in case I misinterpreted something.

Accepted

TLE

Ternay Search is a very cool upgrade/modification on Binary Search logic There are enough resources available on this topic my favorite resource is :-

1. CP Algorithms

This blog will include a different implementation of the approach which I found very cool

    int l=1,r=mx;
    while(r>=l){
        int mid = (r+l)/2;
        int m1 = check(mid);
        int m2 = check(mid+1);
        if(m1>=m2){
            ans = updateAns(and,m1);
            r=mid-1;
        }
        else{
            l=mid+1;
            ans = updateAns(and,m2);
        }
    }

It would make more sense if you study the concept and then solve these 2 problems these are fairly recent problems as well

• Lonely Mountain Dungeons
• My Implementation
• Meeting on the Line
• My Implementation

Would love any input to improve this blog.

You are given an array of integers arr, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Problem Link

Method 1:- Use of Priority Queue(O(nlogn)

        int n = arr.size();
        vector<int> ans;
        priority_queue<pair<int,int>> pq;
        for(int i=0;i<k;i++){
            pq.push({arr[i],i});
        }
        ans.push_back(pq.top().first);
        for(int i=k;i<n;i++){
            pq.push({arr[i],i});
            while(pq.top().second<=i-k){
                pq.pop();
            }
            ans.push_back(pq.top().first);
        }
        return ans; 

Method 2:- Use of Maximum Queue:- In this method we mantain a queue which can tell us the maximum value of the particular Sliding Window

    int n = arr.size();
    vector<int> ans;
    //Implementation of Maximum Queue
    deque<int> q;
    auto add = [&](int x){
        while(!q.empty() && q.back()<x){        //q.back()>x(To convert to Minimum Queue)
            q.pop_back();
        }
        q.push_back(x);
    };
    auto remove = [&](int x){
        if(q.front()==x){
            q.pop_front();
        }
    };
    auto update = [&](){
        ans.push_back(q.front());
    };
    //End of Implementation of Maximum Queue
    for(int i=0;i<n;i++){
        int j=i-k;
        add(arr[i]);
        if(j>=0){
            remove(arr[j]);
        }
        if(i>=k-1){
            update();
        }
    }
    return ans;

Here in Implementation I used Lamda Functions If you dont know you can use normal functins instead it works the same.

You can read about this technique in detail from CP Algorithms :- Minimum Queue The implementation there is for a minimum queue this is for a maximum queue

I am doing a problem which requires similar operation in which we have to find element smaller than x then delete it from multiset then find for another x. I am using an approach that is giving TLE for 10^5 constraints

Problem Link

My Code

Is my method to find that element wrong or is it anything else. PS -> I am not very clear on how to find Elements Lesser than X in set/multiset and its working I used auto it = *lower_bound(st.rbegin(),st.rend(),a[i],greater()); As I saw it in blog can anyone also explain how it works