Comment

avatar username
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;// find_by_order -> iterator of kth value, order_of_key -> number of elements less than k

template <typename T>
struct OrderedMultiset
{
    ordered_set<pair<T, int>> s;
    map<T, int> m;
    void insert(long long element)
    {
        int count = m[element];
        pair<long long, int> p = {element, count};
        m[element]++;
        s.insert(p);
    }

    void erase(long long element)
    {
        if (m.find(element) == m.end())
            return;
        int count = m[element];
        if (count == 1)
            m.erase(element);
        else
            m[element] = count - 1;
        pair<long long, int> eraseP = {element, count - 1};
        s.erase(eraseP);
    }

    int upper_bound(long long element) { return s.order_of_key({element, INT_MAX}); }
    int lower_bound(long long element) { return s.order_of_key({element, -1}); }
    
    long long atIndex(int index) { return (*s.find_by_order(index)).first; }
    bool exists(long long element) { return m.find(element) != m.end(); }
    int occurences(long long element)
    {
        if (m.find(element) == m.end())
        {
            return 0;
        }
        return m[element];
    }
};

void solve()
{
    ll n, q;
    cin >> n >> q;

    vector<ll> arr(n), brr(n);
    for (auto &val : arr)
        cin >> val;
    for (auto &val : brr)
        cin >> val;

    OrderedMultiset<ll> crr, drr;
    for (auto val : arr)
        crr.insert(val);

    for (auto val : brr)
        drr.insert(val);

    ll ans = 1LL;
    for (ll i = 0; i < n; i++) {
        ans = mod_mul(ans, min(crr.atIndex(i), drr.atIndex(i)), MOD);
    }

    cout << ans << " ";

    while (q--)
    {
        ll o, x;
        cin >> o >> x;
        x--;

        if (o == 1)
        {
            ll prev_value = arr[x];
            crr.erase(prev_value);

            arr[x] = (arr[x] + 1) % MOD;
            crr.insert(arr[x]);

            ll idx = crr.lower_bound(arr[x]);

            ll cvalue = crr.atIndex(idx);
            ll dvalue = drr.atIndex(idx);
            ans = mod_div(ans, min(prev_value, dvalue), MOD);
            ans = mod_mul(ans, min(cvalue, dvalue), MOD);
            
        }
        else
        {
            ll prev_value = brr[x];
            drr.erase(prev_value);

            brr[x] = (brr[x] + 1) % MOD;
            drr.insert(brr[x]);

            ll idx = drr.lower_bound(brr[x]);

            ll cvalue = crr.atIndex(idx);
            ll dvalue = drr.atIndex(idx);
            ans = mod_div(ans, min(cvalue, prev_value), MOD);
            ans = mod_mul(ans, min(cvalue, dvalue), MOD);
        }

        cout << ans << " ";
    }
    cout << "\n";
}

why This code giving me TLE for Problem D, am I missing Out something?, I think time complexity for the code will be O(qlogn + nlogn).

The actual rating of this user is 1299.

Original comment.

Statistics