ibrahim_065

THOR

Sep 25th, 2021
785
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#include<bits/stdc++.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <string>
  8. #include <cmath>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <unordered_set>
  13. #include <unordered_map>
  14. #include <stack>
  15. #include <queue>
  16. #include <deque>
  17. #include <iterator>
  18. #include <bitset>
  19. #include <assert.h>
  20. #include <new>
  21. #include <sstream>
  22. #include <time.h>
  23. #include <functional>
  24. #include <numeric>
  25. #include <utility>
  26. #include <limits>
  27. #define endl '\n'
  28. #define READ() freopen("input", "r", stdin)
  29. #define WRITE() freopen("output", "w", stdout)
  30. #define TIME() fprintf(stderr, "\nRuntime: %.10fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC)
  31. #define CLOCK() clock_t tStart = clock()
  32. #define pb push_back
  33. #define vStr vector<string>
  34. #define vi vector<int>
  35. #define vll vector<ll>
  36. #define vLL vector<ll>
  37. #define Mii map<int, int>
  38. #define Msi map<string, int>
  39. #define Mci map<c, int>
  40. #define ll long long int
  41. #define LL long long int
  42. #define ui unsigned int
  43. #define ull unsigned long long int
  44. #define FASTio                       \
  45.    ios_base::sync_with_stdio(false); \
  46.    cin.tie(NULL);
  47. using namespace std;
  48.  
  49. // BIT (Binary Indexed Tree) (Fenwick tree)------------------
  50. void update(vector<int> &BIT, int idx, int value)
  51. {
  52.    // vector<int> BIT length should be main array's (length + 1)
  53.    int len = BIT.size();
  54.    while (idx <= len)
  55.    {
  56.       BIT[idx] += value;
  57.       idx += (idx & -idx);
  58.    }
  59. }
  60.  
  61. int sum(vector<int> &BIT, int idx)
  62. {
  63.    int res = 0;
  64.    while (idx > 0)
  65.    {
  66.       res += BIT[idx];
  67.       idx -= (idx & -idx);
  68.    }
  69.    return res;
  70. }
  71. //===========================================================
  72.  
  73. int main()
  74. {
  75.  
  76.    //---------------------------code_start_from_here-------------------------
  77.  
  78.    FASTio;
  79.    int n, q;
  80.    cin >> n >> q;
  81.    vector<int> mainar(n + 1, 0), bit(n + 2, 0);
  82.    while (q--)
  83.    {
  84.       int a, b;
  85.       cin >> a >> b;
  86.       if (a == 1)
  87.       {
  88.          mainar[b] += 1;
  89.          update(bit, b, 1);
  90.          cout << sum(bit, n) << endl;
  91.       }
  92.       else if (a == 2)
  93.       {
  94.          update(bit, b, -mainar[b]);
  95.          mainar[b] = 0;
  96.          cout << sum(bit, n) << endl;
  97.       }
  98.       else
  99.       {
  100.          int counter = 0;
  101.          for (int i = 1; i <= n; i++)
  102.          {
  103.             if (mainar[i])
  104.             {
  105.                if (counter <= b)
  106.                {
  107.                   if (counter + mainar[i] > b)
  108.                   {
  109.                      update(bit, i, -(b - counter));
  110.                      mainar[i] -= (b - counter);
  111.                      counter += (b - counter);
  112.                   }
  113.                   else
  114.                   {
  115.                      counter += mainar[i];
  116.                      update(bit, i, -mainar[i]);
  117.                      mainar[i] = 0;
  118.                   }
  119.                }
  120.                else
  121.                   break;
  122.             }
  123.          }
  124.          cout << sum(bit, n) << endl;
  125.       }
  126.    }
  127.  
  128.    //---------------------------code_finished--------------------------------
  129.  
  130.    return 0;
  131. }
RAW Paste Data