How many numbers are there from $$$1$$$ to $$$3$$$?

You simply calculate $$$end - start + 1$$$.

/*
"
أَمْ حَسِبْتُمْ أَن تَدْخُلُوا الْجَنَّةَ وَلَمَّا يَأْتِكُم مَّثَلُ الَّذِينَ خَلَوْا مِن قَبْلِكُم ۖ
مَّسَّتْهُمُ الْبَأْسَاءُ وَالضَّرَّاءُ وَزُلْزِلُوا حَتَّىٰ يَقُولَ الرَّسُولُ وَالَّذِينَ آمَنُوا مَعَهُ
مَتَىٰ نَصْرُ اللَّهِ ۗ
أَلَا إِنَّ نَصْرَ اللَّهِ قَرِيبٌ
"
*/

// my template : ideone.com/3q74bT

#include <bits/stdc++.h>
using namespace std;

#define HereWeGo(x) ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define ss second
#define yes "YES"
#define ff first
#define no "NO"



using ll =  long long;
using pll = pair< ll , ll >;
int const N = 1e6 + 6 , mod = 1e9 + 7 , OO = 1e9;


auto solve(){
    ll l , r;cin >> l >> r;
    cout<< r - l + 1;
}

signed main(){
    HereWeGo( from_the_river_to_the_see_palestine_will_be_free );
    int tt = 1;
    cin >> tt ;
    while ( tt-- ){
        solve();
        cout<<'\n';
    }
    return 0;
}

Which is the nearest empty chair to $$$J$$$ in this test: $$$xx-xxxJxxxx-xx$$$?

You want to find the nearest empty chair to $$$J$$$ and print the distance (between $$$J$$$ and the nearest empty chair) — 1, because you want the empty chair to be next to $$$J$$$. If there is no empty chair, you should print -1.

/*
"
أَمْ حَسِبْتُمْ أَن تَدْخُلُوا الْجَنَّةَ وَلَمَّا يَأْتِكُم مَّثَلُ الَّذِينَ خَلَوْا مِن قَبْلِكُم ۖ
مَّسَّتْهُمُ الْبَأْسَاءُ وَالضَّرَّاءُ وَزُلْزِلُوا حَتَّىٰ يَقُولَ الرَّسُولُ وَالَّذِينَ آمَنُوا مَعَهُ
مَتَىٰ نَصْرُ اللَّهِ ۗ
أَلَا إِنَّ نَصْرَ اللَّهِ قَرِيبٌ
"
*/

// my template : ideone.com/3q74bT

#include <bits/stdc++.h>
using namespace std;

#define HereWeGo(x) ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define ss second
#define yes "YES"
#define ff first
#define no "NO"

using ll =  long long;
using pll = pair< ll , ll >;
template<typename T> using min_queue = priority_queue<T, vector<T>, greater<>>;
template<class T> using Graph = vector< vector< T > >;
int const N = 1e6 + 6 , mod = 1e9 + 7 , OO = 1e9;

auto solve(){
    string s;cin >> s;
    int J = (int)s.find( 'J' );
    int res = -1;
    for (int i = J; s[i] ; ++i) {
        if( s[i] == '-' ){
            res = i - J - 1;
            break;
        }
    }
    for (int i = J; ~i ; --i) {
        if( s[i] == '-' ){
            if( res == -1 ) res = J - i - 1;
            
            res = min( res , J - i - 1 );
            break;
        }
    }
    cout << res ;
}

signed main(){
    HereWeGo( from_the_river_to_the_see_palestine_will_be_free );
    int tt = 1;
    cin >> tt ;
    while ( tt-- ){
        solve();
        cout<<'\n';
    }
    return 0;
}

Try to split the problem into two subproblems if $$$z \leq x$$$ and if $$$z > x$$$.

If $$$z > x$$$, how much does the T-shirt cost after already buying $$$y$$$ items?

First, we should buy $$$y$$$ items (in this case, Shazly wins $$$y \cdot x$$$). After this point, we buy an item with a cost of $$$z - x$$$ because when we buy an item, we pay $$$x$$$, and the total decreases by $$$z$$$. So, effectively, we buy the item for $$$z - x$$$. Let's split the problem from this point into two problems:

1. If $$$z - x$$$ is greater than or equal to zero.
2. If $$$z - x$$$ is smaller than zero.

In the first case ($$$z - x \geq 0$$$), the customer can buy any number of items because the total will never decrease. So, if $$$z \geq x$$$, the result will be $$$-1$$$.

In the second case ($$$z - x < 0$$$), we can buy items that make the total ($$$y \cdot x$$$) greater than or equal to zero. We can calculate it by $$$\frac{x \cdot y}{z - x}$$$. So, the result will be $$$y + \frac{x \cdot y}{z - x}$$$, where $$$y$$$ indicates the initial items we buy before starting to get the offer.

/*
"
أَمْ حَسِبْتُمْ أَن تَدْخُلُوا الْجَنَّةَ وَلَمَّا يَأْتِكُم مَّثَلُ الَّذِينَ خَلَوْا مِن قَبْلِكُم ۖ
مَّسَّتْهُمُ الْبَأْسَاءُ وَالضَّرَّاءُ وَزُلْزِلُوا حَتَّىٰ يَقُولَ الرَّسُولُ وَالَّذِينَ آمَنُوا مَعَهُ
مَتَىٰ نَصْرُ اللَّهِ ۗ
أَلَا إِنَّ نَصْرَ اللَّهِ قَرِيبٌ
"
*/

// my template : ideone.com/3q74bT

#include <bits/stdc++.h>
using namespace std;

#define HereWeGo(x) ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define ss second
#define yes "YES"
#define ff first
#define no "NO"



using ll =  long long;
using pll = pair< ll , ll >;
int const N = 1e6 + 6 , mod = 1e9 + 7 , OO = 1e9;

auto solve(){
    ll y , x , z;
    cin >> y >> x >> z;
    if( z <= x ) return void(cout<<-1);
    cout<<y + (y * x / (z - x));
}

signed main(){
    HereWeGo( from_the_river_to_the_see_palestine_will_be_free );
    int tt = 1;
    cin >> tt ;
    while ( tt-- ){
        solve();
        cout<<'\n';
    }
    return 0;
}

You just need to print $$$(x1 + x2) / 2$$$ and $$$(y1 + y2) / 2$$$ (in floating point)

#include <bits/stdc++.h>
using namespace std;
void TANJIR0U();
const int N=1e5+9;

void solve() {
    double x,y,x1,y1;
    cin>>x>>y>>x1>>y1;
    cout<<setprecision(20)<<(x+x1)/2<<" "<<(y+y1)/2;
}

int main() {
    TANJIR0U();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

void TANJIR0U() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

Let $$$n$$$ be the size of the permutation. The number of permutations that can be formed using $$$n$$$ elements is $$$n!$$$.

$$$log(x * y) = log(x) + log(y)$$$

If we want to know how many $$$7$$$s are needed to reach $$$x$$$ to $$$0$$$, we simply get $$$\left(\left\lfloor \log_{7}(x) \right\rfloor + 1\right)$$$. But how do we get $$$\log_{7}(x)$$$ in programming? We can obtain it by binary search or using math rules:

Now you can get $$$\log_{7}(n!)$$$, but take a look at the constraints: $$$n \leq 10^{7}$$$. If you try to calculate the factorial of $$$n$$$ with these constraints, you will encounter overflow. So, we will use the rule $$$log(x * y) = log(x) + log(y)$$$.

/*
"
أَمْ حَسِبْتُمْ أَن تَدْخُلُوا الْجَنَّةَ وَلَمَّا يَأْتِكُم مَّثَلُ الَّذِينَ خَلَوْا مِن قَبْلِكُم ۖ
مَّسَّتْهُمُ الْبَأْسَاءُ وَالضَّرَّاءُ وَزُلْزِلُوا حَتَّىٰ يَقُولَ الرَّسُولُ وَالَّذِينَ آمَنُوا مَعَهُ
مَتَىٰ نَصْرُ اللَّهِ ۗ
أَلَا إِنَّ نَصْرَ اللَّهِ قَرِيبٌ
"
*/

// my template : ideone.com/3q74bT

#include <bits/stdc++.h>
using namespace std;

#define HereWeGo(x) ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define ss second
#define yes "YES"
#define ff first
#define no "NO"



using ll =  long long;
using pll = pair< ll , ll >;
int const N = 1e6 + 6 , mod = 1e9 + 7 , OO = 1e9;


auto solve(){
    int n;
    cin >> n;
    double sum = 1;
    double log7 = log10(7);
    for(int i = 2; i <= n; i++) {
        sum += log10(i) / log7;
    }
    cout << ll(sum);
}

signed main(){
    HereWeGo( from_the_river_to_the_see_palestine_will_be_free );
    int tt = 1;
    //cin >> tt ;
    while ( tt-- ){
        solve();
    }
    return 0;
}

You should try to play in each cell where you can make a move.

You should save the answer for each state you encounter.

Look at hints 1 and 2. If the count of $$$X$$$s is equal to the count of $$$O$$$s, then player $$$X$$$ should play; otherwise, player $$$O$$$ should play.

/*
"
أَمْ حَسِبْتُمْ أَن تَدْخُلُوا الْجَنَّةَ وَلَمَّا يَأْتِكُم مَّثَلُ الَّذِينَ خَلَوْا مِن قَبْلِكُم ۖ
مَّسَّتْهُمُ الْبَأْسَاءُ وَالضَّرَّاءُ وَزُلْزِلُوا حَتَّىٰ يَقُولَ الرَّسُولُ وَالَّذِينَ آمَنُوا مَعَهُ
مَتَىٰ نَصْرُ اللَّهِ ۗ
أَلَا إِنَّ نَصْرَ اللَّهِ قَرِيبٌ
"
*/

// my template : ideone.com/3q74bT

#include <bits/stdc++.h>
using namespace std;

#define HereWeGo(x) ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define ss second
#define yes "YES"
#define ff first
#define no "NO"



using ll =  long long;
using pll = pair< ll , ll >;
int const N = 1e6 + 6 , mod = 1e9 + 7 , OO = 1e9;

int const n = 3;
ll ans = 0;
map< char , char >otherPlayer = { {'X','O'} , {'O','X'} };
map<vector<vector<char>>, int> dp;

bool hasPlayerWon(const vector<vector<char>>& x_o, char player) {
    // Check rows and columns
    for (int i = 0; i < 3; ++i) {
        if ((x_o[i][0] == player && x_o[i][1] == player && x_o[i][2] == player) ||
            (x_o[0][i] == player && x_o[1][i] == player && x_o[2][i] == player)) {
            return true;
        }
    }

    // Check diagonals
    if ((x_o[0][0] == player && x_o[1][1] == player && x_o[2][2] == player) ||
        (x_o[0][2] == player && x_o[1][1] == player && x_o[2][0] == player)) {
        return true;
    }

    return false;
}

int rec(vector< vector< char > >x_o,char player){
    if( hasPlayerWon(x_o,'X') ){
        return 1;
    }
    if( hasPlayerWon(x_o , 'O') ){
        return 0;
    }
    auto res = dp.find(x_o);
    if(res != dp.end())
        return res->second;

    int &re = dp[x_o];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {

            if( x_o[ i ][ j ] == '-' ){
                x_o[ i ][ j ] = player;
                re += rec( x_o , otherPlayer[ player ] );
                x_o[i][j] = '-';
            }

        }
    }
    return re;
}

auto solve(){
    vector< vector< char > >x_o( n , vector< char >( n ) );
    map< char , int >freq;
    for (auto & i : x_o) {
        for (char & j : i) {
            cin >> j;
            if( j != '-' ) freq[ j ]++;
        }
    }
    if( freq[ 'X' ] == freq[ 'O' ] ){
        ans = rec( x_o , 'X' );
    }
    else {
        ans = rec( x_o , 'O' );
    }
    cout<<ans;

}

signed main(){
    HereWeGo( from_the_river_to_the_see_palestine_will_be_free );
    int tt = 1;
    cin >> tt ;
    while ( tt-- ){
        solve();
        cout<<'\n';
    }
    return 0;
}

Try to identify a pattern.

In general, we can place all of our knight pieces on the same color to ensure that none will attack each other. So, the solution will be half the number of all positions available (add one if odd).

However, this solution might not be efficient when the board size is smaller, such as when $$$N$$$ or $$$M$$$ equals 1, when both $$$N$$$ and $$$M$$$ equal 2, or when one dimension is 2 and the other is 3. But these cases are easy to figure out.

#include<bits/stdc++.h>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

using namespace std;

void solve() {
    long long n,m;
    cin>>n>>m;
    if( n == 1 or m == 1){
        cout << max(n,m) << "\n";
    }
    else if(n <= 2 and m <= 2){
        cout << n * m << "\n";
    }
    else if(n * m == 6){
        cout << n * m - 2 << "\n";
    }
    else
        cout << (n * m) / 2 + ((n * m) % 2) << "\n";
}


int main() {
    fast_cin();
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

$$$(1 \leq n \leq 10^{3}, 1 \leq q \leq 10^{3})$$$.

Due to the constraints in the problem, it is easy to simulate what is required. We can create a boolean array of length $$$n + 1$$$ (assuming 1-based indexing, but you can adjust for 0-based indexing) initially, with all positions set to $$$false$$$. When a cut is made at a certain point, we set that position to $$$true$$$. For each query of the second type, we can traverse the entire array and consider the number of consecutive cuts that satisfy the condition.

#include <bits/stdc++.h>
#define notToday ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//#define all(x) x.begin(), x.end()
using ll = long long;
using namespace std;

void T() {
    int n, q;
    cin >> n >> q;
    vector<bool> arr(n + 1);
    arr[n] = true;
    while (q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int x;
            cin >> x;
            arr[x] = true;
        }
        else {
            int l, r, ans = 0;
            cin >> l >> r;
            for(int i = 1, c = 0; i <= n; i++) {
                c++;
                if(arr[i]) {
                    if(c >= l && c <= r)
                        ans++;
                    c = 0;
                }
            }
            cout << ans << '\n';
        }
    }
}

int32_t main() {
    notToday
    int tc = 1;
//    cin >> tc;
    for (int test = 1; test <= tc; ++test) {
        T();
    }
//    cerr << clock() / 1000.0 << " Secs";
    return 0;
}

Alright, let's say we store in a set the points where cuts are made initially, $$$\bf{(0, n)}$$$. Also, we use a data structure called ordered_multiset to store the lengths initially, starting with $$$\bf{(n)}$$$ for the whole paper.

Now, there are three scenarios:

1. $$$\bf{Cutting}$$$ $$$\bf{a}$$$ $$$\bf{piece}$$$ $$$\bf{of}$$$ $$$\bf{paper}$$$: For example, if the set is $$$\bf{(0, 10)}$$$ and we want to cut at point $$$5$$$, we would perform an upper_bound operation for $$$5$$$ to get the points after and before it. Then, we calculate the distances $$$(10 - 5)$$$ and $$$(5 - 0)$$$, erase these distances from the ordered_multiset, and add the new distances $$$(10 - 5)$$$ and $$$(5 - 0)$$$ to maintain the natural order.

2. $$$\bf{Stick}$$$ $$$\bf{the}$$$ $$$\bf{paper}$$$ $$$\bf{again}$$$: If we want to attach a piece of paper at a point $$$x$$$, we perform an upper_bound operation for $$$x$$$, get the points after and before it (e.g., $$$\bf{(0, x, 10)}$$$), erase the distances $$$(10 - x)$$$ and $$$(x - 0)$$$ from the ordered_multiset, and add the new distance $$$(10 - 0)$$$.

3. $$$\bf{Counting}$$$ $$$\bf{the}$$$ $$$\bf{number}$$$ $$$\bf{of}$$$ $$$\bf{papers}$$$ $$$\bf{between}$$$ $$$\bf{l}$$$ $$$\bf{and}$$$ $$$\bf{r}$$$: We simply can use ordered_multiset to know how many segments verify the condition.

#include <bits/stdc++.h>
#define notToday ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//#define all(x) x.begin(), x.end()
using ll = long long;
using namespace std;

//-----------------------------------------------------------------------------------------------------------------------------------------------------------
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace __gnu_pbds;


template<typename K, typename V, typename Comp = std::less<K>>
using ordered_map = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;
template<typename K, typename Comp = std::less<K>>
using ordered_set = ordered_map<K, null_type, Comp>;

template<typename K, typename V, typename Comp = std::less_equal<K>>
using ordered_multimap = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;
template<typename K, typename Comp = std::less_equal<K>>
using ordered_multiset = ordered_multimap<K, null_type, Comp>;

//----------------------------------------------------------------------------------------------------------------------------------------------------------

void T() {
    int n, q;
    cin >> n >> q;

    ordered_multiset<int> len;
    len.insert(n);

    set<int> arr {0, n};

    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int i;
            cin >> i;
            if( i == n ) continue;

            auto it = arr.find(i);
            if(it == arr.end()){
                auto r = arr.upper_bound(i);
                auto l = --r;
                ++r;
                int d = *r - *l;
                arr.insert(i);

                len.erase(len.lower_bound(d - 1));
                len.insert(*r - i);
                len.insert(i - *l);
            }
            else {
                auto r = *(++it); --it;
                auto l = *(--it);
                arr.erase(++it);

                int d = r - i;
                len.erase(len.lower_bound(d - 1));
                d = i - l;
                len.erase(len.lower_bound(d - 1));

                len.insert(r - l);
            }
        }
        else {
            int l, r;
            cin >> l >> r;
            int ans = int(len.order_of_key(r + 1)) - int(len.order_of_key(l));
            cout << ans << '\n';
        }
    }
}

int32_t main() {
    notToday
    int tc = 1;
//    cin >> tc;
    for (int test = 1; test <= tc; ++test) {
        T();
    }
//    cerr << clock() / 1000.0 << " Secs";
    return 0;
}

Let $$$a$$$ and $$$t$$$ be the contestants' numbers.

Since Ali Azzam and TANJIR0U are both very good, one of them may make it to the finals. You need to reserve at least one seat in each round until the end of the competition, which is equal to $$$\log_2(n)$$$.

But before they duel each other, you will need to reserve one extra seat since both of the will be dueling. To do so, you need to calculate how many rounds will happen before they meet.

Two contestants are competing against each other if $$$\lceil \frac{t}{2^{roundNumber - 1}}\rceil = \lceil \frac{a}{2^{roundNumber - 1}}\rceil$$$

To find the number of rounds, you can keep doing ceil division for both $$$a$$$ and $$$t$$$ until $$$\lceil \frac{t}{2}\rceil = \lceil \frac{a}{2}\rceil$$$.

The answer is $$$\log_2(n)$$$ + numberOfRoundBeforeMeeting.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ll n, a, t;
    cin >> n >> a >> t;
    ll ans = 0;
    while ((a+1)/2 != (t+1)/2){
        ans++;
        a = (a+1)/2;
        t = (t+1)/2;
    }
    cout << ans + (ll)log2(n) << endl;
}

If $$$a$$$ and $$$b$$$ are both less than or equal $$$c$$$, When does $$$2^a + 2^b = 2^c$$$ ?

Let's say that a, b and c are the three elements chosen sorted in ascending order $$$(a \leq b \leq c)$$$ In order for $$$2^a + 2^b$$$ to be more than $$$2^c$$$, b has to be equal to c, because $$$(x + anyNumber < x)$$$ so to count the number of elements such that $$$(2^a + 2^b > 2^c)$$$

We use frequency array $$$cnt$$$ to count the number of occurrences of each element

We either choose $$$3$$$ elements equal to $$$c$$$

or

$$$2$$$ elements equal to $$$c$$$ and $$$1$$$ element smaller than $$$c$$$

Now we need to find the number ways to choose $$$a,b$$$ and $$$c$$$ such that $$$2^a + 2^b = 2^c$$$

We can notice that

$$$2^x + 2^x = 2 * 2^x = 2^{x + 1}$$$

So we need to count the number of ways to choose $$$1$$$ element equal to $$$c$$$ and $$$2$$$ element equal to $$$c - 1$$$ i.e.

So the answer is

=

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n];
    vector<ll> fre(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        fre[a[i]]++;
    }
    ll ans = 0;
    ll pre = 0;
    for (int i = 0; i <= n; ++i){
        ll x = fre[i];
        // Number of way to choose 3 equal elements
        ans += (x * (x - 1) * (x - 2))/6;
        if (i){
            // Number of ways to choose a 1 smaller number and 2 equal
            ans += ((x * (x - 1))/2) * pre;
 
            // Number of ways to choose a 2 smaller number and 1 equal
            ans += (fre[i - 1] * (fre[i - 1] - 1))/2 * x;
        }
        pre += fre[i];
    }
    cout << ans << '\n';
}

Let $$$minHomingAttacks_i$$$ be the minimum number of homing attacks Sonic needs to use to reach and destroy the $$$i$$$-th enemy.

$$$minHomingAttacks_i = min(minHomingAttacks_{i-1},minHomingAttacks_{i-2},minHomingAttacks_{i-3}, \dots, minHomingAttacks_{x}) + h_i$$$

Where $$$x$$$ is the first index such that $$$a[i] - a[x] \leq k$$$.

Naively calculating the minimum in the recurrence relation for each $$$i$$$ would take $$$O(n^2)$$$ time, which exceeds the given constraints.

To get around this we need to be able to get $$$minHomingAttacks_j$$$, the element in the $$$minHomingAttacks$$$ array with the minimum value such that $$$x \leq j < i$$$.

There are multiple ways to achieve this, but our solution uses a queue to store all the elements that achieve the above condition and we keep all the elements in the queue in a set to be able to get the smallest solution.

Both the queue and the set store pairs of $$$minHomingAttacksValue, a_i$$$.

Since the array $$$a$$$ is sorted, the queue is also sorted, we keep popping the front of the queue until the front is greater than or equal to $$$a_i - k$$$ and each element popped gets removed from the set.

The first element in the set is the minimum element.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;

    vector<ll> robotPositions(n);
    vector<ll> robotHealth(n);
    vector<ll> minHomingAttacks(n);

    for (int i = 0; i < n; ++i){
        cin >> robotPositions[i];
    }

    for (int i = 0; i < n; ++i){
        cin >> robotHealth[i];
    }

    queue<pair<ll, ll>> potentialTargets; // F: minAttacks, S: distance
    set<pair<ll, ll>> validTargets;
    potentialTargets.push({0, 0});
    validTargets.insert({0, 0});

    for (int i = 0; i < n; ++i) {
        while (robotPositions[i] - potentialTargets.front().second > k) {
            validTargets.erase(potentialTargets.front());
            potentialTargets.pop();
        }

        minHomingAttacks[i] = validTargets.begin()->first + robotHealth[i];

        potentialTargets.push({minHomingAttacks[i], robotPositions[i]});
        validTargets.insert({minHomingAttacks[i], robotPositions[i]});
    }

    cout << minHomingAttacks[n - 1] << "\n";
}

What graph algorithm are we going to use?

You can solve this problem using the Disjoint-Set Union (DSU) algorithm. For each query, you check if $$$x$$$ is connected by Tom and $$$y$$$ is connected by Jerry, or if $$$x$$$ is connected by Jerry and $$$y$$$ is connected by Tom. If either of these conditions holds, the relation is toxic; otherwise, it is valid.

#include <bits/stdc++.h>
using namespace std;
void TANJIR0U();
const int N=1e5+9;

struct DSU{
    int parent[N];
    DSU(){
        for(int i = 0 ; i<N ; i++)
        {
            parent[i]=i;
        }
    }
    int find_leader(int i){
        if(parent[i]==i)
        {
            return i;
        }
        return parent[i]=find_leader(parent[i]);
    }
    bool same_group(int x, int y){
        int leader1=find_leader(x);
        int leader2=find_leader(y);
        return leader1==leader2;
    }
    void unite(int x, int y){

        if(y==0 || y==1){ // leader should always be Tom or Jerry
            swap(x,y);
        } 
        parent[y]=x;
        
    }
};


void solve() {
    int n;
    cin>>n;
    DSU dsu;
    for(int i=0,x,y;i<n;i++){
        cin>>x>>y;
        int leader1 = dsu.find_leader(x);
        int leader2 = dsu.find_leader(y);
        if(leader1+leader2==1){ // must be Tom and Jerry (0 & 1)
            cout<<"toxic"<<endl;
        }else{
            cout<<"valid"<<endl;
            dsu.unite(leader1,leader2);
        }
    }
}

int main() {
    TANJIR0U();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

void TANJIR0U() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

The topic used is Lazy Propagation in Segment Tree

#include <bits/stdc++.h>
#define notToday ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//#define all(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int mod = 1e9 + 7;

class SegmentTree {
    struct node {
        node *l, *r;
        ll v, E = 0;
        explicit node(ll v = {}, node *l = nullptr, node *r = nullptr)
                : v(v), r(r), l(l) {
            if(l) merge(this);
        }
    };
    node *root;
    int size;

    inline static ll nrm(ll x) {
        if(x < -mod || x >= mod) x %= mod;
        if(x < 0) return x + mod;
        return x;
    }
    inline static void merge(node *x) {
        x->v = nrm(x->l->v + x->r->v);
    }
    inline static ll merge(ll v1, ll v2) {
        return nrm(v1 + v2);
    }
    inline static void edit(node *x, int &lx, int &rx) {
        if(x->E) {
            if(x->l) {
                x->l->E += x->E;
                x->l->E = nrm(x->l->E);
            }
            if(x->r) {
                x->r->E += x->E;
                x->r->E = nrm(x->r->E);
            }
            x->v += nrm(x->E * (rx - lx + 1));
            x->v = nrm(x->v);
            x->E = 0;
        }
    }
    node *build(int lx, int rx) {
        if(lx == rx) return new node;
        int m = (lx + rx) >> 1;
        return new node({}, build(lx, m), build(m + 1, rx));
    }
    ll get(node *x, int lx, int rx, int l, int r) {
        edit(x, lx, rx);
        if(lx > r || l > rx) return 0;
        if(lx >= l && rx <= r) return x->v;
        int m = (lx + rx) >> 1;
        return merge(get(x->l, lx, m, l, r), get(x->r, m + 1, rx, l, r));
    }
    void set(node *x, int lx, int rx, int i, ll val) {
        edit(x, lx, rx);
        if(lx == rx) return void(x->v = nrm(val));
        int m = (lx + rx) >> 1;
        i <= m? set(x->l, lx, m, i, val): set(x->r, m + 1, rx, i, val);
        merge(x);
    }
    void setRange(node *x, int lx, int rx, int l, int r, ll val) {
        edit(x, lx, rx);
        if(lx > r || l > rx) return;
        if(lx >= l && rx <= r) return x->E = nrm(val), edit(x, lx, rx);
        int m = (lx + rx) >> 1;
        setRange(x->l, lx, m, l, r, val), setRange(x->r, m + 1, rx, l, r, val);
        merge(x);
    }
    void del(node *x) {
        if(x){
            del(x->l), del(x->r);
            delete x;
        }
    }
public://based index 0
    explicit SegmentTree(int n) : size(n) {
        root = build(0, size);
    }
    ~SegmentTree(){
        del(root);
    }
    void set(int i, ll v) {
        set(root, 0, size, i, v);
    }
    ll getRange(int l, int r) {
        return get(root, 0, size, l, r);
    }
    void plusRange(int l, int r, ll val) {
        if(l > r) return;
        setRange(root, 0, size, l, r, val);
    }
};

int n, m, start, e;
int res = 0;
vector<array<int, 4>> op;
void rec(int x, int i = 0) {
    if(x == e) {
        res++;
        return;
    }
    if(i == op.size()) return;
    if(x >= op[i][0] && x <= op[i][1]) {
        for(int k = op[i][2]; k <= op[i][3]; k++) {
            rec(k, i + 1);
        }
    }
    rec(x, i + 1);
}

void T() {
    cin >> n >> m >> start >> e;

    SegmentTree dp(n);
    dp.set(start, 1);

    ll ans = 0;
    while(m--) {
        int l, r, l1, r1;
        cin >> l >> r >> l1 >> r1;
        op.push_back({l, r, l1, r1});

        ll sum = dp.getRange(l, r);
        dp.plusRange(l1, r1, sum);

        ans += dp.getRange(e, e);
        ans %= mod;
        dp.set(e, 0);

//        res = 0;
//        rec(start);
//        assert(res == ans);
        cout << ans << '\n';
    }
}

int32_t main() {
    notToday
    int tc = 1;
//    cin >> tc;
    for (int test = 1; test <= tc; ++test) {
        T();
    }
//    cerr << clock() / 1000.0 << " Secs";
    return 0;
}

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using ll = long long;

const int N = 1e6 + 5, M = 1003, MOD = 1e9 + 7, oo = 1e8;

#define Azzam ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ll modSum(ll a, ll b) {
    a = (a % MOD + MOD) % MOD, b = (b % MOD + MOD) % MOD;
    return (a + b) % MOD;
}

/*_________________________________________________________________________________________________________*/

ll Tree[4 * N], lazy[4 * N], arr[N];
int n ;

void propagate(int node, int l, int r) {
    if (lazy[node] == 0)
        return;
    Tree[node] = modSum(lazy[node]*(r - l + 1) , Tree[node]);
    if (l != r) {
        lazy[node * 2] = modSum(lazy[node] , lazy[node * 2]);
        lazy[node * 2 + 1] = modSum(lazy[node] , lazy[node*2 + 1]);
    }
    lazy[node] = 0;
}

void update(int node, int l, int r, int st, int en, ll val) {
    propagate(node, l, r);
    if (st > en || st > r || en < l)
        return;
    if (l >= st && r <= en) {
        lazy[node] = (lazy[node] + val) % MOD;
        propagate(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2, l, mid, st, en, val);
    update(node * 2 + 1, mid + 1, r, st, en, val);
    Tree[node] = modSum(Tree[node * 2], Tree[node * 2 + 1]);
}

ll query(int node, int l, int r, int st, int en) {
    propagate(node, l, r);
    if (st > en || st > r || en < l)
        return 0;
    if (l >= st && r <= en)
        return   Tree[node];
    int mid = (l + r) / 2;
    return modSum(query(node * 2, l, mid, st, en), query(node * 2 + 1, mid + 1, r, st, en));
}
void update(int l, int r,int val){
    return update(1, 0, n-1,l,r,val);
}
ll query(int l, int r) {
    return query(1,0,n-1,l,r);
}

void solve() {
    int m , s , e;
    cin >> n >> m >> s >> e;
    --e , --s;
    update(s , s , 1);
    for (int i = 0; i < m; ++i) {
        int l , r , a , b;
        cin >> l >> r >> a >> b;
        --l , --r , --a , --b;
        ll q = query( l ,r) , q2 = 0 ;
        if(e >= l and e <= r)
            q2 = query( e , e);
        update(a , b , q - q2);
        cout << query(e , e) << '\n';
    }
}


int32_t main() {
    Azzam
    int tt = 1;
//    cin >> tt;
    while (tt--) {
        solve();
    }
}