Dang_Quan_10_Tin

Untitled

Jun 26th, 2020
243
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #define NguyenDangQuan the_author
  2.  
  3. #include <bits/stdc++.h>
  4. #define all(x) x.begin(),x.end()
  5. #define mset(x, i) memset(x,i,sizeof(x))
  6. #define elif else if
  7. #define heap priority_queue
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define ld long double
  12. #define ll long long
  13. #define ull unsigned long long
  14. #define task "codef"
  15. using namespace std;
  16.  
  17. int typetest;
  18. inline void fastIOfileinput(){
  19.     ios_base:: sync_with_stdio(0);
  20.     cin.tie(0);
  21.     cout.tie(0);
  22.     typetest = 0;
  23. }
  24.  
  25. struct segment{
  26.     int v;
  27. };
  28.  
  29. const int N = 1e6;
  30. int n, q;
  31. int v = 0;
  32. segment st[(N << 2) + 2];
  33.  
  34. void upd(int id, int in, int l, int r){
  35.     if(id < l || id > r) return;
  36.     else if(id == l && id == r ){
  37.         ++st[in].v;
  38.         return;
  39.     }
  40.     upd(id, in * 2, l, (l + r) / 2);
  41.     upd(id, in * 2 + 1, (l + r) / 2 + 1, r);
  42.     st[in].v = st[in << 1].v + st[in << 1 | 1].v;
  43. }
  44.  
  45. void update(int id, int in, int l, int r){
  46.     if(l == r && st[in].v + v >= id){
  47.         --st[in].v;
  48.         return;
  49.     }
  50.     if(st[in << 1].v + v >= id)
  51.         update(id, in << 1, l, (l + r) / 2);
  52.     else
  53.         v += st[in << 1].v,
  54.         update(id, in << 1 | 1, (l + r) / 2 + 1, r);
  55.     st[in].v = st[in << 1].v + st[in << 1 | 1].v;
  56. }
  57.  
  58. int que(int id, int l, int r){
  59.     if(l == r && st[id].v != 0){
  60.         return l;
  61.     }
  62.     if(st[id << 1].v > 0)
  63.         return que(id << 1, l, (l + r) / 2);
  64.     return que(id << 1 | 1, (l + r) / 2 + 1, r);
  65. }
  66.  
  67. void Enter(){
  68.     cin >> n >> q;
  69.     //build(1, 1, n);
  70.     for(int i = 1; i <= n; ++i){
  71.         int v; cin >> v;
  72.         upd(v, 1, 1, n);
  73.     }
  74.     while(q--){
  75.         int vv; cin >> vv;
  76.         if(vv > 0)
  77.             upd(vv, 1, 1, n);
  78.         else{
  79.                 v = 0;
  80.             update(abs(vv), 1, 1, n);
  81.         }
  82.     }
  83. }
  84.  
  85. void solve(){
  86.     if(st[1].v == 0)
  87.         cout << 0;
  88.     else{
  89.         cout << que(1, 1, n);
  90.     }
  91. }
  92.  
  93. main(){
  94.     fastIOfileinput();
  95.     if(typetest){
  96.         int t;
  97.         cin >> t;
  98.         while(t--){
  99.             Enter();
  100.             solve();
  101.         }
  102.     }
  103.     else{
  104.         Enter();
  105.         solve();
  106.     }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment