fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define TASK "text"
  4. #define all(x) x.begin(), x.end()
  5. #define compact(v) sort(all(v)), v.erase(unique(all(v)), v.end())
  6. #define fi first
  7. #define se second
  8. #define ___Speacial_ signed main()
  9. using namespace std;
  10. typedef long long ll;
  11. typedef pair<int, int> ii;
  12. typedef pair<ll, int> Ii;
  13. typedef pair<int, ll> iI;
  14. typedef vector<int> vi;
  15. typedef vector<ii> vii;
  16. template<class T> using minHeap = 
  17. priority_queue<T, vector <T>, greater<T>>;
  18.  
  19. const int N = 3e5 + 5;
  20. const int maxn = 1e6 + 7;
  21.  
  22. struct node {
  23.     int sum; int mSuf;
  24.     node (int _val = 0) : sum(_val), mSuf(_val) { } 
  25. } tree[maxn * 4 + 2];
  26. int a[maxn + 2], b[maxn + 2];
  27. int d[maxn + 2];
  28.  
  29. int n, m, nQueries;
  30.  
  31. node operator + (const node &left, const node &right) {
  32.     node newNode;
  33.     newNode.sum = left.sum + right.sum;
  34.     newNode.mSuf = max(left.mSuf + right.sum, right.mSuf);
  35.     return newNode;
  36. }
  37.  
  38. void build(int id, int l, int r) {
  39.     if (l == r) {
  40.         tree[id] = d[l];
  41.         return;
  42.     }
  43.  
  44.     int mid = (l + r) >> 1;
  45.     build(id << 1, l, mid);
  46.     build(id << 1 | 1, mid + 1, r);
  47.  
  48.     tree[id] = tree[id << 1] + tree[id << 1 | 1];
  49. }
  50.  
  51. void modify(int id, int l, int r, int pos, int delta) {
  52.     if (l == r) {
  53.         tree[id].sum += delta;
  54.         tree[id].mSuf += delta;
  55.         return;
  56.     }
  57.  
  58.     int mid = (l + r) >> 1;
  59.     if (pos <= mid) modify(id << 1, l, mid, pos, delta);
  60.         else modify(id << 1 | 1, mid + 1, r, pos, delta);
  61.  
  62.     tree[id] = tree[id << 1] + tree[id << 1 | 1];
  63. }
  64.  
  65. int walk(int id, int l, int r, int sum) {
  66.     if (tree[id].mSuf + sum <= 0) return -1;
  67.     if (l == r) return l;
  68.  
  69.     int mid = (l + r) >> 1;
  70.     int res = walk(id << 1 | 1, mid + 1, r, sum);
  71.     if (res != -1) return res;
  72.     return walk(id << 1, l, mid, sum + tree[id << 1 | 1].sum);
  73. }
  74.  
  75. void process(void) {
  76.     cin >> n >> m;
  77.     for (int i = 1; i <= n; ++i) {
  78.         cin >> a[i]; d[a[i]]++;
  79.     }
  80.     for (int i = 1; i <= m; ++i) {
  81.         cin >> b[i]; d[b[i]]--;
  82.     }
  83.  
  84.     build(1, 1, maxn);
  85.     cin >> nQueries; 
  86.     while (nQueries--) {
  87.         int type, i, val;
  88.         cin >> type >> i >> val;
  89.  
  90.         if (type & 1) {
  91.             modify(1, 1, maxn, a[i], -1);
  92.             modify(1, 1, maxn, a[i] = val, +1);
  93.         }
  94.  
  95.         else {
  96.             modify(1, 1, maxn, b[i], +1);
  97.             modify(1, 1, maxn, b[i] = val, -1);
  98.         }
  99.  
  100.         cout << walk(1, 1, maxn, 0) << '\n';
  101.     }
  102. }
  103.  
  104. ___Speacial_ {
  105.     ios::sync_with_stdio(0);
  106.     cin.tie(0); cout.tie(0);
  107.     if(fopen(TASK".inp","r")){
  108.         freopen(TASK".inp","r",stdin);
  109.         freopen(TASK".out","w",stdout);
  110.     }
  111.     int testcases = 1; //    cin >> testcases;
  112.     for (int o_O = 1; o_O <= testcases; ++o_O) {
  113. //        cout << "Case #" << o_O << ":\n"; 
  114.         process();
  115.         if (o_O != testcases) cout << '\n';
  116.     }
  117.  
  118.     cerr << "[Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms.]\n";
  119.     return (0 ^ 0);
  120. }
Success #stdin #stdout #stderr 0.02s 36972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
[Time elapsed: 0.014829 ms.]
https://ideone.com/Wl2hoY
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!