fork download
copy 
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp> // Common file
  3. //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_int_update
  4.  
  5. using namespace std;
  6. //using namespace __gnu_pbds;
  7. //typedef tree< pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_int_update>
  8. //ordered_set;
  9. int dx[] = {0, 1, 0, -1};
  10. int dy[] = {-1, 0, 1, 0};
  11. #define X first
  12. #define Y second
  13. #define int long long int 
  14. const int MAXN = (int)1e6 + 10;
  15. const int MOD = 1000000007;
  16.  
  17. int K, n;
  18. int tree[4 * MAXN];
  19.  
  20. void build(int id, int tl, int tr){
  21.     if(tl > tr){
  22.         return;
  23.     }
  24.     if( tl == tr ){
  25.         tree[id] = K;
  26.         return;
  27.     }
  28.     int tm = (tl + tr) / 2;
  29.     build(id * 2, tl, tm);
  30.     build(id * 2 + 1, tm + 1, tr);
  31.     tree[id] = tree[id * 2] + tree[id * 2 + 1];
  32. }
  33.  
  34. void update(int id, int tl, int tr, int val){
  35.     if(tl > tr){
  36.         return;
  37.     }
  38.     if( tl == tr ){
  39.         tree[id] -= val;
  40.         return;
  41.     }
  42.     //check if we can go left side
  43.     int tm = (tl + tr) / 2;
  44.     if(tree[id * 2] >= val){
  45.         update(id * 2, tl, tm, val);
  46.     } else if( tree[id * 2 + 1] >= val ){
  47.         update(id * 2 + 1, tm + 1, tr, val);
  48.     }
  49.     //after updation change its parent
  50.     tree[id] = tree[id * 2] + tree[id * 2 + 1];
  51. }
  52.  
  53. int res = 0, used = 0;
  54.  
  55. void get_ans(int id, int tl, int tr){
  56.     if( tl > tr ){
  57.         return;
  58.     }
  59.     if(tl == tr){
  60.         if(tree[id] < K)
  61.             res += tree[id], used++;
  62.         return;
  63.     }
  64.     int tm = (tl + tr)  / 2;
  65.     if((tm - tl + 1) * K != tree[id * 2] )
  66.         get_ans(id * 2, tl, tm);
  67.     if(  (tr - (tm + 1) + 1) * K  != tree[id * 2 + 1] )
  68.         get_ans(id * 2 + 1, tm + 1, tr);
  69. }
  70.  
  71. void solve(){
  72.     cin >> K >> n;
  73.     build(1, 0, n - 1);
  74.     for(int i = 0; i < n; ){
  75.         string ch; cin >> ch;
  76.         if( ch == "b" ){
  77.             int times; cin >> times;
  78.             int num; cin >> num;
  79.             for(int k = 0; k < times; ++k, ++i){
  80.                 update(1, 0, n - 1, num);
  81.             }
  82.         } else {
  83.             int num = stoi(ch);
  84.             update(1, 0, n - 1, num);
  85.             ++i;
  86.         }
  87.         /*for(int i = 1; i <= 7; ++i){
  88.             cout << tree[i] << " ";
  89.         }
  90.         cout << '\n';*/
  91.     }
  92.     res = 0, used = 0;
  93.     get_ans(1, 0, n - 1);
  94.     cout << used << " " << res << '\n';
  95.  
  96.  
  97.  
  98.  
  99.  
  100. }
  101.  
  102. int32_t main(){
  103.     ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); 
  104.     int t; cin >> t;
  105.     while(t--)
  106.         solve();
  107.     return 0;
  108. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
2
100
3
50
25
70
100
4
50
b 2 40
20
stdout
copy 
2 55
2 50
https://ideone.com/IM7ApX
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!