Advertisement
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;
- struct FenwickTree {
- vector<int> bit;// binary indexed tree
- int n;
- FenwickTree(int n) {
- this->n = n;
- bit.assign(n, 0);
- }
- FenwickTree(vector<int> a) : FenwickTree(a.size()) {
- for (size_t i = 0; i < a.size(); i++)
- add(i, a[i]);
- }
- int sum(int r) {
- int ret = 0;
- for (; r >= 0; r = (r & (r + 1)) - 1)
- ret += bit[r];
- return ret;
- }
- int sum(int l, int r) {
- return sum(r) - sum(l - 1);
- }
- void add(int idx, int delta) {
- for (; idx < n; idx = idx | (idx + 1))
- bit[idx] += delta;
- }
- };
- int main() {
- FenwickTree 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.add(results[who], -1);
- }
- results[who] = result;
- tree.add(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
Advertisement