Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define NguyenDangQuan the_author
- #include <bits/stdc++.h>
- #define all(x) x.begin(),x.end()
- #define mset(x, i) memset(x,i,sizeof(x))
- #define elif else if
- #define heap priority_queue
- #define fi first
- #define se second
- #define pb push_back
- #define ld long double
- #define ll long long
- #define ull unsigned long long
- #define task "codef"
- using namespace std;
- int typetest;
- inline void fastIOfileinput(){
- ios_base:: sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- typetest = 0;
- }
- struct segment{
- int v;
- };
- const int N = 1e6;
- int n, q;
- int v = 0;
- segment st[(N << 2) + 2];
- void upd(int id, int in, int l, int r){
- if(id < l || id > r) return;
- else if(id == l && id == r ){
- ++st[in].v;
- return;
- }
- upd(id, in * 2, l, (l + r) / 2);
- upd(id, in * 2 + 1, (l + r) / 2 + 1, r);
- st[in].v = st[in << 1].v + st[in << 1 | 1].v;
- }
- void update(int id, int in, int l, int r){
- if(l == r && st[in].v + v >= id){
- --st[in].v;
- return;
- }
- if(st[in << 1].v + v >= id)
- update(id, in << 1, l, (l + r) / 2);
- else
- v += st[in << 1].v,
- update(id, in << 1 | 1, (l + r) / 2 + 1, r);
- st[in].v = st[in << 1].v + st[in << 1 | 1].v;
- }
- int que(int id, int l, int r){
- if(l == r && st[id].v != 0){
- return l;
- }
- if(st[id << 1].v > 0)
- return que(id << 1, l, (l + r) / 2);
- return que(id << 1 | 1, (l + r) / 2 + 1, r);
- }
- void Enter(){
- cin >> n >> q;
- //build(1, 1, n);
- for(int i = 1; i <= n; ++i){
- int v; cin >> v;
- upd(v, 1, 1, n);
- }
- while(q--){
- int vv; cin >> vv;
- if(vv > 0)
- upd(vv, 1, 1, n);
- else{
- v = 0;
- update(abs(vv), 1, 1, n);
- }
- }
- }
- void solve(){
- if(st[1].v == 0)
- cout << 0;
- else{
- cout << que(1, 1, n);
- }
- }
- main(){
- fastIOfileinput();
- if(typetest){
- int t;
- cin >> t;
- while(t--){
- Enter();
- solve();
- }
- }
- else{
- Enter();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment