Advertisement
rudolf222222

Untitled

Nov 15th, 2022
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  1. #include <cmath>
  2. #include <iomanip>
  3. #include <iostream>
  4. #include <vector>
  5. class Fenwick3D {
  6.  public:
  7.   Fenwick3D(int n) {
  8.     // tree_.assign(n, 0);   // tree_
  9.     arr_.assign(n, 0);    // how many guys are there for that time
  10.     pages_.assign(n, 0);  // track of time of each user
  11.   }
  12.   /*int GetSum(int right) const {
  13.     int value = PrefixSum(right);
  14.     return value;
  15.   }*/
  16.   double UserCount(int index) const {
  17.     if (index > static_cast<int>(pages_.size())) {
  18.       return 0;
  19.     }
  20.     if (pages_[index] == 0) {
  21.       return 0;
  22.     }
  23.     const int kIndex = static_cast<int>(arr_.size());
  24.     // double all_users = static_cast<double>(GetSum(kIndex - 1));
  25.     if (all_users_ == 0) {
  26.       return 0;
  27.     }
  28.     if (all_users_ == 1) {
  29.       return 1;
  30.     }
  31.     double users = static_cast<double>(PrefSum(index));
  32.     // double all_users = static_cast<double>(PrefSum(kIndex - 1));
  33.     users /= (all_users_ - 1);
  34.     return users;
  35.   }
  36.   void Update(int user, int new_time) {
  37.     if (user > static_cast<int>(pages_.size())) {
  38.       pages_.resize(user + 1, 0);
  39.     }
  40.     int old_time = pages_[user];
  41.     if (old_time != 0) {
  42.       UpdateUsers(old_time, -1);
  43.     }
  44.     if (old_time == 0) {
  45.       all_users_++;
  46.     }
  47.     // int delta = value - old_time;
  48.     // UpdateDelta(user, delta);
  49.     UpdateUsers(new_time, 1);
  50.     pages_[user] = new_time;
  51.   }
  52.  
  53.  private:
  54.   static int F(int i) { return (i & (i + 1)); }
  55.   static int G(int i) { return (i | (i + 1)); }
  56.   int PrefSum(int right) const { return PrefCount(pages_[right] - 1); }
  57.   int PrefCount(int value) const {
  58.     int answer = 0;
  59.     for (int x = value; x >= 0; x = F(x) - 1) {
  60.       answer += arr_[x];
  61.     }
  62.     return answer;
  63.   }
  64.   void UpdateUsers(int user, int delta) {
  65.     if (user > static_cast<int>(arr_.size())) {
  66.       arr_.resize(user * 2, 0);
  67.     }
  68.     const int kSize = static_cast<int>(arr_.size());
  69.     for (int x = user; x < kSize; x = G(x)) {
  70.       arr_[x] += delta;
  71.     }
  72.   }
  73.   // std::vector<int> tree_;
  74.   std::vector<int> arr_;
  75.   std::vector<int> pages_;
  76.   double all_users_;
  77. };
  78.  
  79. void Requests() {
  80.   int n = 0;
  81.   std::cin >> n;
  82.   Fenwick3D fenwick(n);
  83.   std::string req;
  84.   int r = 0;
  85.   int l = 0;
  86.   for (int k = 0; k < n; ++k) {
  87.     std::cin >> req;
  88.     if (req == "RUN") {
  89.       std::cin >> l >> r;
  90.       fenwick.Update(l - 1, r);
  91.     } else if (req == "CHEER") {
  92.       std::cin >> l;
  93.       double sum = fenwick.UserCount(l - 1);
  94.       std::cout << std::fixed << std::setprecision(6) << sum << "\n";
  95.     }
  96.   }
  97. }
  98. int main() {
  99.   Requests();
  100.   return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement