1810D - Climbing the Tree - CodeForces Solution

// Shibam Debnath
// 2022

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, int> pint;
typedef pair<double, double> pdd;
typedef vector<vector<int>> vvi;
typedef vector<vector<int>> vvll;

#define f(i, s, n) for (int i = s; i < n; i++)
#define rf(i, s, n) for (int i = n - 1; i >= s; i--)
#define endl "\n"
#define print(x) cout << x << endl
#define debug(x) cout << x << endl
#define mp make_pair
#define pb push_back
#define INF 2e18
#define vll(n) vector<long long> v(n)
#define dp(n, m, val) vector<vector<int>> dp(n, vector<int>(m, val))

#define inp(vec)        \
    for (auto &x : vec) \
        cin >> x;
#define printv(vec)     \
    for (auto &x : vec) \
        cout << x << " ";

#define hare_krishna                  \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

#define SORT(s) sort(s.begin(), s.end());

void solve()
{
    int n;
    cin >> n;

    int mx_height = -1;
    int mn_height = -1;

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;

        if (x == 1)
        {
            int a, b, day;
            cin >> a >> b >> day;

            int diff = a - b;
            int last_night = diff * (day - 1);
            int first_daylight = last_night + b + 1;
            if (last_night == 0)
                first_daylight = 0;
            int last_daylight = last_night + a;
            if (mn_height == -1)
            {
                mn_height = first_daylight;
                mx_height = last_daylight;
                cout << 1 << " ";
            }
            else
            {
                if (last_daylight < mn_height || first_daylight > mx_height)
                    cout << 0 << " ";
                else
                {
                    mn_height = max(first_daylight, mn_height);
                    mx_height = min(mx_height, last_daylight);
                    cout << 1 << " ";
                }
            }

            // cout << "input " << a << " " << b << " " << day << endl;

            // calculate day required
            // int gap = a - b;
            // if (gap < 0)
            // {
            //     cout << 0 << " ";
            //     continue;
            // }

            // int last_day = (gap) * (day - 1);
            // int l = last_day + b + 1;

            // if (last_day == 0)
            //     l = 0;
            // int r = (gap) * (day - 1) + a;

            // //  << l << " " << r << " prev height " << mn_height << " " << mx_height << endl;
            // if (mx_height == -1)
            // {
            //     mn_height = l;
            //     mx_height = r;
            // }
            // else
            // {
            //     // check if satisfies prev assumptions or not
            //     if (l > mx_height or r < mn_height)
            //     {
            //         cout << 0 << " ";
            //         continue;
            //     }
            //     else
            //     {
            //         l = max(l, mn_height);
            //         r = min(r, mx_height);
            //     }
            // }
            // cout << 1 << " ";
        }
        else
        {
            int a, b;
            cin >> a >> b;

            // int t = mn_height - a;
            // int dd = (a - b);
            // t = (t + (dd - 1)) / (a - b);
            // t++;
            // if (t <= 0)
            //     t = 1;
            // int tt = mx_height - a;
            // tt = (tt + (dd - 1)) / (a - b);
            // tt++;
            // if (tt <= 0)
            //     tt = 1;
            // if (tt != t)
            //     cout << -1 << " ";
            // else
            //     cout << t << " ";

            // cout << "height " << mn_height << " " << mx_height << endl;
            // cout << "input " << a << " " << b << endl;

            // usi din pahuch jayega

            if (mn_height == -1)
            {
                // not possible
                cout << -1 << " ";
                continue;
            }

            int gap = a - b;
            int last_day_mx = ((mn_height - a - 1) + (gap)) / gap;
            int min_days_req = last_day_mx + 1;
            if (min_days_req <= 0)
                min_days_req = 1;

            int last_day_mxx = ((mx_height - a - 1) + (gap)) / gap;
            int max_days_req = last_day_mxx + 1;
            if (max_days_req <= 0)
                max_days_req = 1;

            // find days req to get to the mn_height to max_height
            if (min_days_req == max_days_req)
            {
                cout << min_days_req << " ";
            }
            else
            {
                cout << -1 << " ";
            }
        }
    }
    cout << endl;
}

signed main()
{
    hare_krishna;

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}