mfgnik

Untitled

May 31st, 2020
873
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <vector>
  4. #include <iomanip>
  5. using namespace std;
  6.  
  7. class Fenwick {
  8. public:
  9.     Fenwick(int n) : size_(n), tree_(n){}
  10.  
  11.     Fenwick(vector<int> a) : Fenwick(a.size()) {
  12.         for (size_t index = 0; index < a.size(); index++) {
  13.             increment(index, a[index]);
  14.         }
  15.     }
  16.  
  17.     int sum(int right) {
  18.         int s = 0;
  19.         for (; right >= 0; right = (right & (right + 1)) - 1) {
  20.             s += tree_[right];
  21.         }
  22.         return s;
  23.     }
  24.  
  25.     void increment(int index, int delta) {
  26.         for (; index < size_; index |= (index + 1))
  27.             tree_[index] += delta;
  28.     }
  29.  
  30. private:
  31.     vector<int> tree_;
  32.     int size_;
  33. };
  34.  
  35.  
  36. int main() {
  37.     Fenwick tree(43000);
  38.     int q;
  39.     std::cin >> q;
  40.     std::unordered_map<int, int> results;
  41.     int amount = 0;
  42.     while (q > 0) {
  43.         std::string command;
  44.         std::cin >> command;
  45.         if (command == "RUN") {
  46.             int who, result;
  47.             std::cin >> who >> result;
  48.             if (results.count(who) == 0) {
  49.                 ++amount;
  50.             } else {
  51.                 tree.increment(results[who], -1);
  52.             }
  53.             results[who] = result;
  54.             tree.increment(results[who], 1);
  55.         } else {
  56.             int who;
  57.             std::cin >> who;
  58.             if (results.count(who) == 0) {
  59.                 std::cout << 0 << "\n";
  60.             } else if (amount == 1) {
  61.                 std::cout << 1 << "\n";
  62.             } else {
  63.                 int a = tree.sum(results[who] - 1);
  64.                 std::cout << std::setprecision(6) << static_cast<double>(a) / (amount - 1) << "\n";
  65.             }
  66.         }
  67.         --q;
  68.     }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment