SHARE
TWEET

Untitled

a guest Jun 22nd, 2019 1,097 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6.  
  7. const int MAXN = 3e5 + 7;
  8. const int MAXV = 3 * MAXN;
  9.  
  10. int n, m;
  11. int a[MAXN], b[MAXN];
  12.  
  13. int q;
  14. int t[MAXN], p[MAXN], x[MAXN];
  15.  
  16. void read() {
  17.     cin >> n >> m;
  18.     for (int i = 0; i < n; ++i) {
  19.         cin >> a[i];
  20.     }
  21.     for (int i = 0; i < m; ++i) {
  22.         cin >> b[i];
  23.     }  
  24.     cin >> q;
  25.     for (int i = 0; i < q; ++i) {
  26.         cin >> t[i];
  27.         if (t[i] <= 2) {
  28.             cin >> p[i] >> x[i];
  29.             --p[i];
  30.         }
  31.     }  
  32. }  
  33.  
  34. int u = 0;
  35. int v[MAXV];
  36.  
  37. void compr() {
  38.     for (int i = 0; i < n; ++i) {
  39.         v[u++] = a[i];
  40.     }  
  41.     for (int i = 0; i < m; ++i) {
  42.         v[u++] = b[i];
  43.     }  
  44.     for (int i = 0; i < q; ++i) {
  45.         if (t[i] <= 2) {
  46.             v[u++] = x[i];
  47.         }  
  48.     }  
  49.     sort(v, v + u);
  50.     u = unique(v, v + u) - v;
  51.     for (int i = 0; i < n; ++i) {
  52.         a[i] = lower_bound(v, v + u, a[i]) - v;
  53.     }  
  54.     for (int i = 0; i < m; ++i) {
  55.         b[i] = lower_bound(v, v + u, b[i]) - v;
  56.     }  
  57.     for (int i = 0; i < q; ++i) {
  58.         if (t[i] <= 2) {
  59.             x[i] = lower_bound(v, v + u, x[i]) - v;
  60.         }  
  61.     }  
  62. }  
  63.  
  64. int tree[MAXV << 2], add[MAXV << 2];
  65.  
  66. void push(int v) {
  67.     tree[v * 2 + 1] += add[v];
  68.     add[v * 2 + 1] += add[v];
  69.     tree[v * 2 + 2] += add[v];
  70.     add[v * 2 + 2] += add[v];
  71.     add[v] = 0;
  72. }  
  73.  
  74. void upd(int v, int tl, int tr, int l, int r, int x) {
  75.     if (tr < l || r < tl) {
  76.         return;
  77.     }  
  78.     if (l <= tl && tr <= r) {
  79.         tree[v] += x;
  80.         add[v] += x;
  81.         return;
  82.     }  
  83.     int tm = (tl + tr) >> 1;
  84.     push(v);
  85.     upd(v * 2 + 1, tl, tm, l, r, x);
  86.     upd(v * 2 + 2, tm + 1, tr, l, r, x);
  87.     tree[v] = max(tree[v * 2 + 1], tree[v * 2 + 2]);
  88. }
  89.  
  90. int get(int v, int tl, int tr) {
  91.     if (tl == tr) {
  92.         return tl;
  93.     }  
  94.     int tm = (tl + tr) >> 1;
  95.     push(v);
  96.     if (tree[v * 2 + 2] >= 1) {
  97.         return get(v * 2 + 2, tm + 1, tr);
  98.     }  
  99.     else {
  100.         return get(v * 2 + 1, tl, tm);
  101.     }  
  102. }  
  103.  
  104. void add1(int x) {
  105.     //cout << x << ' ' << 1 << '\n';
  106.     upd(0, 0, MAXV, 0, x, 1);
  107. }
  108.  
  109. void del1(int x) {
  110.     //cout << x << ' ' << -1 << '\n';
  111.     upd(0, 0, MAXV, 0, x, -1);
  112. }
  113.  
  114. void upd1(int p, int x) {
  115.     del1(a[p]);
  116.     a[p] = x;
  117.     add1(a[p]);
  118. }  
  119.  
  120. void add2(int x) {
  121.     //cout << x << ' ' << -1 << '\n';
  122.     upd(0, 0, MAXV, 0, x, -1);
  123. }
  124.  
  125. void del2(int x) {                  
  126.     //cout << x << ' ' << 1 << '\n';
  127.     upd(0, 0, MAXV, 0, x, 1);
  128. }  
  129.  
  130. void upd2(int p, int x) {
  131.     del2(b[p]);
  132.     b[p] = x;
  133.     add2(b[p]);
  134. }  
  135.  
  136. int get() {
  137.     if (tree[0] >= 1) {
  138.         return get(0, 0, MAXV);
  139.     }  
  140.     else {
  141.         return -1;
  142.     }  
  143. }  
  144.  
  145. void solve() {
  146.     compr();
  147.     for (int i = 0; i < n; ++i) {
  148.         add1(a[i]);
  149.     }  
  150.     for (int i = 0; i < m; ++i) {
  151.         add2(b[i]);
  152.     }  
  153. }
  154.  
  155. void print() {
  156.     for (int i = 0; i < q; ++i) {
  157.         if (t[i] == 1) {
  158.             upd1(p[i], x[i]);
  159.         }  
  160.         else {
  161.             upd2(p[i], x[i]);
  162.         }  
  163.         {
  164.             int ans = get();
  165.             if (ans == -1) {
  166.                 cout << "-1\n";
  167.             }  
  168.             else {
  169.                 cout << v[ans] << '\n';
  170.             }  
  171.         }  
  172.     }  
  173. }
  174.  
  175. signed main() {
  176.     ios_base::sync_with_stdio(0);
  177.     cin.tie(0);
  178.  
  179.     read();
  180.     solve();
  181.     print();
  182.  
  183.     return 0;
  184. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top