Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <iomanip>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. const ll X = 1000000 + 10000;
  9. ll fenvals[X + 1];
  10.  
  11. void update(ll i, ll change) {
  12.     while (i <= X) {
  13.         fenvals[i] += change;
  14.         i |= i + 1;
  15.     }
  16. }
  17.  
  18. ll psum(ll i) {
  19.     int sum = 0;
  20.     while (i >= 0) {
  21.         sum += fenvals[i];
  22.         i &= i + 1;
  23.         i--;
  24.     }
  25.     return sum;
  26. }
  27.  
  28. int main() {
  29.     ios::sync_with_stdio(false), cin.tie(0);
  30.     double count = 0;
  31.     while (true) {
  32.         string oper;
  33.         cin >> oper;
  34.         if (oper == "QUIT") {
  35.             break;
  36.         }
  37.         double raw_x;
  38.         cin >> raw_x;
  39.         ll x = floor(100*raw_x + 0.5);
  40.         if (oper == "BID") {
  41.             update(x, 1);
  42.         } else if (oper == "DEL") {
  43.             update(x, -1);
  44.         } else {
  45.             ll k;
  46.             cin >> k;
  47.             count += min(k, psum(X) - psum(x - 1));
  48.         }
  49.     }
  50.     count /= 100;
  51.     cout << fixed << setprecision(2) << count;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement