Weighted Merge Interval

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

#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define F first
#define S second
#define PI 3.1415926535897932384626
#define sz(x) ((int)(x).size())

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vull> vvull;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vs> vvs;

/************************************************** DEBUGGER *******************************************************************************************************/

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(ld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(vector <vector<T>> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }

/*******************************************************************************************************************************************************************/

mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
    uniform_int_distribution<int> uid(0,lim-1);
    return uid(rang);
}

const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;

ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
                         while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }

ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }

/******************************************************************************************************************************/

vpii merge_intervals(vpii &v, int n) {
    vpii res;
    if(n == 0) return res;

    sort(v.begin(), v.end());
    res.pb(v[0]);

    for(int i = 1; i < n; i++) {
        int x1 = v[i].F;
        int y1 = v[i].S;

        int x2 = res[res.size() - 1].F;
        int y2 = res[res.size() - 1].S;

        if(y2 >= x1 or x1 == y2 + 1) res[res.size() - 1].S = max(y2, y1);
        else res.pb({x1, y1});
    }

    return res;
}

vpii find_ans(vvi &v) {
    int n = sz(v);
    if(n == 0) return vpii();

    vvi tmp;

    for(int i = 0; i < n; i++) {
        tmp.pb({v[i][0], -1, v[i][2]});
        tmp.pb({v[i][1], 1, v[i][2]});
    }

    sort(tmp.begin(), tmp.end());

    map<pii, int> m;

    int i = 0, wt = 0, st = -1, ed = -1;
    n = sz(tmp);

    while(i + 1 < n) {
        if(tmp[i][1] == -1) {
            if(tmp[i+1][1] == -1) {
                if(tmp[i+1][0] == tmp[i][0]) {
                    st = tmp[i][0];
                    wt = tmp[i][2];
                    while(i + 1 < n and tmp[i][0] == tmp[i+1][0] and tmp[i][1] == -1 and tmp[i+1][1] == -1) {
                        wt += tmp[i+1][2];
                        i++;
                    }

                    if(i < n) {
                        if(tmp[i][1] == 1) {
                            ed = tmp[i][1];
                            wt += tmp[i][2];

                            int j = i + 1;
                            while(j + 1 < n and (tmp[j][0] == tmp[j+1][0]) and (tmp[j][1] == 1 and tmp[j+1][1] == 1)) {
                                wt += tmp[i+1][2];
                                j++;
                            }

                            m[{st, ed}] = wt;
                            i = j;
                            st = ed = -1;
                            wt = 0;
                        }
                    }
                }

                else i++;
            }

            else {
                st = tmp[i][0];
                ed = tmp[i+1][0];
                wt = tmp[i][2] + tmp[i+1][2];

                int j = i + 1;
                while(j + 1 < n and (tmp[j][0] == tmp[j+1][0]) and (tmp[j][1] == 1 and tmp[j+1][1] == 1)) {
                    wt += tmp[j+1][2];
                    j++;
                }

                m[{st, ed}] = wt;
                i = j;
                st = ed = -1;
                wt = 0;
            }
        }

        else i++;
    }

    for(int i = 0; i < sz(v); i++) {
        if(m.find({v[i][0], v[i][1]}) == m.end()) {
            m[{v[i][0], v[i][1]}] = v[i][2];
        }
    }

    int mx = -1;
    for(auto x: m) mx = max(mx, x.S);

    vpii tmp2;
    for(auto x: m) {
        if(x.S == mx) tmp2.pb(x.F);
    }

    return merge_intervals(tmp2, sz(tmp2));
}

void solve()
{
    int n; cin >> n;
    vvi v(n, vi(3));

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

    vpii res = find_ans(v);
    for(auto x: res) cout << x.F << ", " << x.S << "\n";
    cout << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif

    // #ifndef ONLINE_JUDGE
    //      freopen("error.txt", "w", stderr);
    // #endif

    int t = 1;
    // int test = 1;
    // cin >> t;
    while(t--) {
        // cout << "Case #" << test++ << ": ";
        solve();
    }

    return 0;
}