Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <unordered_map>
- #include <vector>
- #include <iomanip>
- using namespace std;
- class Fenwick {
- public:
- Fenwick(int n) : size_(n), tree_(n){}
- Fenwick(vector<int> a) : Fenwick(a.size()) {
- for (size_t index = 0; index < a.size(); index++) {
- increment(index, a[index]);
- }
- }
- int sum(int right) {
- int s = 0;
- for (; right >= 0; right = (right & (right + 1)) - 1) {
- s += tree_[right];
- }
- return s;
- }
- void increment(int index, int delta) {
- for (; index < size_; index |= (index + 1))
- tree_[index] += delta;
- }
- private:
- vector<int> tree_;
- int size_;
- };
- int main() {
- Fenwick tree(43000);
- int q;
- std::cin >> q;
- std::unordered_map<int, int> results;
- int amount = 0;
- while (q > 0) {
- std::string command;
- std::cin >> command;
- if (command == "RUN") {
- int who, result;
- std::cin >> who >> result;
- if (results.count(who) == 0) {
- ++amount;
- } else {
- tree.increment(results[who], -1);
- }
- results[who] = result;
- tree.increment(results[who], 1);
- } else {
- int who;
- std::cin >> who;
- if (results.count(who) == 0) {
- std::cout << 0 << "\n";
- } else if (amount == 1) {
- std::cout << 1 << "\n";
- } else {
- int a = tree.sum(results[who] - 1);
- std::cout << std::setprecision(6) << static_cast<double>(a) / (amount - 1) << "\n";
- }
- }
- --q;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment