You may also want to add this line at the very top of your code #pragma GCC optimize("O3"). It helped an O(√n^3) code pass when it shouldn't have.

Well I didn't focus on constant factor so like

I just realized that. This is because map lookup times is O(logn), which means you are doing an additional O(logn) to the O(nlogn) which makes constant factor much worse.

I provide you with this unhackable(or supposedly unhackable) unordered map template:

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
      static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
        x = (x^(x>>30))*0xbf58476d1ce4e5b9;
        x = (x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
      }

      size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = rng();
        return splitmix64(x+FIXED_RANDOM);
      }
};

template<typename T, typename V> using safe_map = unordered_map<T, V, custom_hash>;

This is because endl flushes the output as well as prints a new line. You need to make sure to flush the output (by doing endl or "\n"+cout.flush();) for interactive problems, but "\n" is better for anything that isn't interactive.

I would recommend reading this for more detail: https://usaco.guide/general/fast-io