Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- using std::cin, std::cout, std::endl;
- int main() {
- int q;
- cin >> q;
- std::multiset<int> elements;
- auto median = elements.end();
- int n = 0;
- for (int op = 0; op < q; ++op) {
- char type;
- int x;
- cin >> type >> x;
- if (type == '+') {
- elements.insert({x, op});
- if (x >= *median && n % 2 == 0) {
- ++median;
- } else if (x < *median && n % 2 == 1) {
- --median;
- }
- ++n;
- } else {
- auto it = elements.lower_bound(x);
- if (it == median) {
- if (n % 2 == 0) {
- ++median;
- } else {
- --median;
- }
- } else if (*it > *median && n % 2 == 1) {
- --median;
- } else if (*it < *median && n % 2 == 0) {
- ++median;
- }
- elements.erase(it);
- --n;
- }
- if (n == 0) {
- cout << "set is empty" << endl;
- } else {
- cout << "median is " << *median << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement