Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <iomanip>
- #include <iostream>
- #include <vector>
- class Fenwick3D {
- public:
- Fenwick3D(int n) {
- // tree_.assign(n, 0); // tree_
- arr_.assign(n, 0); // how many guys are there for that time
- pages_.assign(n, 0); // track of time of each user
- }
- /*int GetSum(int right) const {
- int value = PrefixSum(right);
- return value;
- }*/
- double UserCount(int index) const {
- if (index > static_cast<int>(pages_.size())) {
- return 0;
- }
- if (pages_[index] == 0) {
- return 0;
- }
- const int kIndex = static_cast<int>(arr_.size());
- // double all_users = static_cast<double>(GetSum(kIndex - 1));
- if (all_users_ == 0) {
- return 0;
- }
- if (all_users_ == 1) {
- return 1;
- }
- double users = static_cast<double>(PrefSum(index));
- // double all_users = static_cast<double>(PrefSum(kIndex - 1));
- users /= (all_users_ - 1);
- return users;
- }
- void Update(int user, int new_time) {
- if (user > static_cast<int>(pages_.size())) {
- pages_.resize(user + 1, 0);
- }
- int old_time = pages_[user];
- if (old_time != 0) {
- UpdateUsers(old_time, -1);
- }
- if (old_time == 0) {
- all_users_++;
- }
- // int delta = value - old_time;
- // UpdateDelta(user, delta);
- UpdateUsers(new_time, 1);
- pages_[user] = new_time;
- }
- private:
- static int F(int i) { return (i & (i + 1)); }
- static int G(int i) { return (i | (i + 1)); }
- int PrefSum(int right) const { return PrefCount(pages_[right] - 1); }
- int PrefCount(int value) const {
- int answer = 0;
- for (int x = value; x >= 0; x = F(x) - 1) {
- answer += arr_[x];
- }
- return answer;
- }
- void UpdateUsers(int user, int delta) {
- if (user > static_cast<int>(arr_.size())) {
- arr_.resize(user * 2, 0);
- }
- const int kSize = static_cast<int>(arr_.size());
- for (int x = user; x < kSize; x = G(x)) {
- arr_[x] += delta;
- }
- }
- // std::vector<int> tree_;
- std::vector<int> arr_;
- std::vector<int> pages_;
- double all_users_;
- };
- void Requests() {
- int n = 0;
- std::cin >> n;
- Fenwick3D fenwick(n);
- std::string req;
- int r = 0;
- int l = 0;
- for (int k = 0; k < n; ++k) {
- std::cin >> req;
- if (req == "RUN") {
- std::cin >> l >> r;
- fenwick.Update(l - 1, r);
- } else if (req == "CHEER") {
- std::cin >> l;
- double sum = fenwick.UserCount(l - 1);
- std::cout << std::fixed << std::setprecision(6) << sum << "\n";
- }
- }
- }
- int main() {
- Requests();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement