首先注意在题给条件下，第 i 秒的 x_i, y_i 的取值变化最多有 O(n) 种，即总共有 O(n) 种不同的不悦值。例如，对 [1,100] 区间并上 [10,1000] 区间，能获得不同取值的子区间只有 [1,9],[10,100],[101,1000]，这三个区间内的每秒带来的不悦值必然是相等的。因为要输出最早，所以只需要考虑每个区间的左端点即可。

不妨离散化，将取值范围为 [1,10^9] 的区间范围压缩至 [1,n] 的范围。即将原本的数值 val 降低为它的排序排名 rank_{val}。这样就不会 MLE 了。具体实现时，可以通过 sort+unique / map 等方法离散化。也可以直接开 set/map 离散下标的数据结构。

现在考虑下一个子问题，即计算不悦值。我们发现 (x+y)!(x+1)(y+1) 非常大，远超 long long，且事实上 n! 也超过了 double 乃至 long double 的最大值，所以直接计算肯定是会溢出的。并且也不能通过增设模数即计算 (x+y)!(x+1)(y+1)\bmod p，因为模意义下无法比较大小。如果开高精度，多次计算有 TLE 和 MLE 的风险(显然，设计算 t 位高精度，单次准确计算加减的复杂度至少是 O(t)，准确计算乘法的复杂度至少是 O(t\sqrt t)(FFT 丢精度，不保证 100% 准确)，比较大小复杂度也是 O(t))。

注意到要比较 (x_1+y_1)!(x_1+1)(y_1+1) 与 (x_2+y_2)!(x_2+1)(y_2+1)，即两边取对数，比较 \ln(x_1+y_1)!+\ln(x_1+1)+\ln(y_1+1) 与 \ln(x_2+y_2)!+\ln(x_2+1)+\ln(y_2+1)。显然取对数后数量级是不会溢出的，虽然损失了准确值(但是答案也没要求算准确值)，但仍可以比较大小。显然 x+y\le n，故可以 O(n) 预处理出所有的阶乘对数 \ln n!=\ln(n-1)!+\ln n，然后就可以方便比较大小了。值得注意 \ln 函数计算是 O(1) 的。

总复杂度为 O(n\log n)(即离散化的复杂度)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
const ll mn = 1e5 + 10;
ll n, ans;
db f[mn], mx = -1;
map<ll, ll> s[3];
db g(ll x, ll y)
{
    return log(x + 1) + log(y + 1) + f[x + y];
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    f[0] = 0; // ln(0!)=0
    for (ll i = 1; i <= n; ++i)
    {
        f[i] = f[i - 1] + log(i); // ln(i!)
    }
    for (ll l, r, c; n; --n)
    {
        cin >> l >> r >> c;
        s[c][l]++;
        s[c][r + 1]--;
        s[3 - c][l] += 0, s[3 - c][r + 1] += 0; //使得s[1],s[2]拥有的下标一致
    }
    s[1][0] += 0, s[2][0] += 0;
    auto i = s[1].begin(), j = i;
    for (++i; i != s[1].end(); ++i, ++j)
    {
        ll i2 = i->first, j2 = j->first;
        s[1][i2] += s[1][j2], s[2][i2] += s[2][j2];
        ll x = s[1][i2], y = s[2][i2];
        db res = g(x, y);
        if (res > mx + 1e-8)
        {
            mx = res;
            ans = i2;
        }
    }
    cout << ans;
    return 0;
}