p311.ans1
======================
HAPPY
UNHAPPY
HAPPY

=================
p311.ans2
======================
UNHAPPY
HAPPY

=================
p311.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class KeyT, class T, T (*merge_func)(T, T), uint64_t (*rng)()>
struct TreapNode {
    KeyT key;
    T data, subtree;
    uint64_t prior;
    size_t size;
    TreapNode *left, *right;

    TreapNode(KeyT key, T data)
        : key(key), data(data), left(nullptr), right(nullptr), size(1) {
        prior = rng();
    }

    void pull() {
        subtree = data;
        size = 1;
        if(left) {
            subtree = merge_func(left->subtree, subtree);
            size += left->size;
        }
        if(right) {
            subtree = merge_func(subtree, right->subtree);
            size += right->size;
        }
    }

    friend pair<TreapNode*, TreapNode*> split(TreapNode* t, KeyT key) {
        if(!t) {
            return {nullptr, nullptr};
        }
        if(key < t->key) {
            auto [left, t_left] = split(t->left, key);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] = split(t->right, key);
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend pair<TreapNode*, TreapNode*> split_by_size(
        TreapNode* t, size_t size
    ) {
        if(!t) {
            return {nullptr, nullptr};
        }
        if(t->left && t->left->size >= size) {
            auto [left, t_left] = split_by_size(t->left, size);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] = split_by_size(
                t->right, size - 1 - (t->left ? t->left->size : 0)
            );
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend TreapNode* merge(TreapNode* l, TreapNode* r) {
        if(!l || !r) {
            return l ? l : r;
        } else if(l->prior > r->prior) {
            l->right = merge(l->right, r);
            l->pull();
            return l;
        } else {
            r->left = merge(l, r->left);
            r->pull();
            return r;
        }
    }

    friend TreapNode* unordered_merge(TreapNode* l, TreapNode* r) {
        if(!l) {
            return r;
        }
        if(!r) {
            return l;
        }
        if(l->prior < r->prior) {
            swap(l, r);
        }
        auto [t1, t2] = split(r, l->key);
        l->left = unordered_merge(l->left, t1);
        l->right = unordered_merge(l->right, t2);
        l->pull();
        return l;
    }

    friend void insert_in(TreapNode*& t, TreapNode* it) {
        if(!t) {
            t = it;
        } else if(it->prior > t->prior) {
            auto [t1, t2] = split(t, it->key);
            it->left = t1;
            it->right = t2;
            t = it;
        } else {
            insert_in(it->key < t->key ? t->left : t->right, it);
        }
        t->pull();
    }

    friend TreapNode* erase_from(
        TreapNode*& t, KeyT key, bool delete_node = false
    ) {
        T return_data;
        if(t->key == key) {
            auto tmp = t;
            t = merge(t->left, t->right);

            return_data = tmp->data;
            if(delete_node) {
                delete tmp;
            }
        } else {
            return_data =
                erase_from(key < t->key ? t->left : t->right, key, delete_node);
        }
        if(t) {
            t->pull();
        }
        return return_data;
    }
};

template<class KeyT, class T, T (*merge_func)(T, T)>
class Treap {
  public:
    static uint64_t rng() {
        static mt19937_64 static_rng(random_device{}());
        return static_rng();
    }

    using Node = TreapNode<KeyT, T, merge_func, Treap::rng>;

    void _pull_all(Node* t) {
        if(t) {
            _pull_all(t->left);
            _pull_all(t->right);
            t->pull();
        }
    }

    Node* root;

    Treap() { root = nullptr; }
    Treap(const vector<KeyT, T>& a) { build_cartesian_tree(a); }

    void build_cartesian_tree(const vector<pair<KeyT, T>>& a) {
        root = nullptr;
        vector<Node*> st;
        for(const auto& [key, val]: a) {
            Node* new_node = new Node(key, val);
            Node* last = nullptr;
            while(!st.empty() && st.back()->prior < new_node->prior) {
                last = st.back();
                st.pop_back();
            }

            if(last) {
                new_node->left = last->right;
            }

            if(st.empty()) {
                root = new_node;
            } else {
                if(new_node->val < st.back()->val) {
                    st.back()->left = new_node;
                } else {
                    st.back()->right = new_node;
                }
            }
            st.push_back(new_node);
        }

        _pull_all(root);
    }

    void insert(KeyT key, T data) {
        Node* new_node = new Node(key, data);
        insert_in(root, new_node);
    }

    void erase(KeyT key) { return erase_from(root, key); }

    friend Treap<KeyT, T, merge_func> merge_treaps(
        Treap<KeyT, T, merge_func> l, Treap<KeyT, T, merge_func> r
    ) {
        Treap<KeyT, T, merge_func> res;
        res.root = unordered_merge(l.root, r.root);
        return res;
    }
};

pair<int64_t, int64_t> plus_func(
    pair<int64_t, int64_t> a, pair<int64_t, int64_t> b
) {
    return {a.first + b.first, a.second + b.second};
}

using TreapWithCount = Treap<int64_t, pair<int64_t, int64_t>, plus_func>;
using Node = TreapWithCount::Node;

pair<Node*, Node*> split_by_count(Node* t, int64_t k) {
    if(!t) {
        return {nullptr, nullptr};
    }
    if(t->left && t->left->subtree.first >= k) {
        auto [left, t_left] = split_by_count(t->left, k);
        t->left = t_left;
        t->pull();
        return {left, t};
    } else {
        k -= (t->left ? t->left->subtree.first : 0);
        if(k < t->data.first) {
            Node* new_left = new Node(t->key, {k, k * t->key});
            t->data.first -= k;
            t->data.second = t->data.first * t->key;

            insert_in(t->left, new_left);
            new_left = t->left;
            t->left = nullptr;
            t->pull();
            return {new_left, t};
        }

        auto [t_right, new_right] = split_by_count(t->right, k - t->data.first);
        t->right = t_right;
        t->pull();
        return {t, new_right};
    }
}

void solve() {
    // Keep the available ice-cream in a treap keyed by price. A node groups all
    // pieces at one price as data = {count, count * price}; each subtree
    // aggregates subtree = {total count, total cost} via plus_func, so the
    // cheapest k pieces always live in the leftmost part by key order.
    //
    // ARRIVE n c inserts a node for price c (insert_in merges equal keys is not
    // needed because we never query by exact key; duplicate prices simply
    // coexist as separate nodes). BUY n t calls split_by_count, which peels off
    // exactly the n cheapest pieces, splitting a price bucket in two when the
    // boundary falls inside it. If that left part has exactly n pieces and its
    // total cost is at most t we keep the split (student buys, HAPPY) and the
    // remaining treap becomes t2; otherwise we merge the pieces back and report
    // UNHAPPY.

    TreapWithCount t;

    string type;
    int64_t arg1, arg2;
    while(cin >> type >> arg1 >> arg2) {
        if(type == "ARRIVE") {
            t.insert(arg2, {arg1, arg1 * arg2});
        } else {
            auto [t1, t2] = split_by_count(t.root, arg1);
            if(!t1 || t1->subtree.second > arg2 || t1->subtree.first != arg1) {
                t.root = merge(t1, t2);
                cout << "UNHAPPY\n";
            } else {
                t.root = t2;
                cout << "HAPPY\n";
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p311.in1
======================
ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000

=================
p311.in2
======================
ARRIVE 10 1
ARRIVE 20 2   
ARRIVE 30 3
BUY 60 100
BUY 60 200

=================
statement.txt
======================
311. Ice-cream Tycoon
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You've recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers.

The day is described with a sequence of queries. Each query can be either ARRIVE n c, meaning that a supplier has delivered n pieces of ice-cream priced c each to you, or BUY n t, meaning that a student wants to buy n pieces of ice-cream, having a total of t money. The latter is processed as follows: in case n cheapest pieces of ice-cream you have cost no more than t (together), you sell those n cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream.

For each student, output HAPPY if she gets her ice-cream, and UNHAPPYif she doesn't.

Input
The input file contains between 1 and 105 queries (inclusive), each on a separate line. The queries are formatted as described above, either ARRIVE n c or BUY n t, 1 ≤ n, c ≤ 106, 1 ≤ t ≤ 1012.

Output
For each BUY-query output one line, containing either the word HAPPY or the word UNHAPPY (answers should be in the same order as the corresponding queries).

Example(s)
sample input
sample output
ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000
HAPPY
UNHAPPY
HAPPY

=================
