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).
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).