Youngling tournament

input/code.cpp: In function 'void solve()':
input/code.cpp:147:6: warning: unused variable 'lo' [-Wunused-variable]
  int lo = 0;
      ^
input/code.cpp:148:6: warning: unused variable 'hi' [-Wunused-variable]
  int hi = pos;
      ^

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N = 1<<17;
struct Node {
    pair<ll, ll> val;
    ll prior;
    int cnt;
    ll sum;
    ll ma;
    Node * left;
    Node * right;
    Node(ll v, ll i) {
	val = {v, i};
	sum = 0;
	ma = 0;
	prior = rand();
	cnt = 1;
	left = right = NULL;
    }
};
Node * root;
int cnt(Node * a) {
    if(a == NULL) return 0;
    return a->cnt;
}
ll sum(Node * a) {
    if(a == NULL) return 0;
    return a->sum;
}
ll ma(Node * a) {
    if(a == NULL) return 0;
    return a->ma;
}
void upd(Node * a) {
    if(a == NULL) return;
    a->cnt = cnt(a->left) + cnt(a->right) + 1;
    a->sum = sum(a->left) + sum(a->right) + a->val.F;
    a->ma = max(ma(a->left), max(ma(a->right), a->val.F));
}
void split(Node* k, Node*& l, Node*& r, int c) {
    if(k == NULL) {
	l = r = NULL;
    }
    else {
	if(cnt(k->left) + 1 <= c) {
	    split(k->right, k->right, r, c - cnt(k->left)-1);
	    l = k;
	}
	else {
	    split(k->left, l, k->left, c);
	    r = k;
	}
    }
    upd(k);
}
void print(Node * a) {
    if(a == NULL) return;
    print(a->left);
    cout<<a->val.F<<' ';
    print(a->right);
}
void merge(Node*& k, Node* l, Node* r) {
    if(l == NULL) {
	k = r;
    }
    else if(r == NULL) {
	k = l;
    }
    else {
	if(l->prior < r->prior) {
	    merge(l->right, l->right, r);
	    k = l;
	}
	else {
	    merge(r->left, l, r->left);
	    k = r;
	}
    }
    upd(k);
}
int n;
ll getSum(Node * k, int x, int y, int cSum) {
    if(k == NULL) return 0;
    //cout<<k->val.F<<endl;
    int l = cSum;
    int r = cSum + cnt(k) - 1;
    if(l > y || r < x) return 0;
    if(l >= x && r <= y) {
	return k->sum;
    }
    ll mid = cSum + cnt(k->left);
    ll q = getSum(k->left, x, y, cSum);
    ll w = getSum(k->right, x, y, cSum+cnt(k->left)+1);
    if(mid >= x && mid <= y) {
	q += k->val.F;
    }
    return q + w;
}
ll getMax(Node * k, int x, int y, int cSum) {
    if(k == NULL) return -1e18;
    int l = cSum;
    int r = cSum + cnt(k) - 1;
    if(l > y || r < x) return -1e18;
    if(l >= x && r <= y) {
	return k->ma;
    }
    ll mid = cSum + cnt(k->left);
    ll q = getMax(k->left, x, y, cSum);
    ll w = getMax(k->right, x, y, cSum+cnt(k->left)+1);
    if(mid >= x && mid <= y) {
	q = max(q, k->val.F);

    }
    return max(q,w);
}
int find(Node * a, ll sum, ll cSum, ll q) {
    ll pos = cSum + cnt(a->left) + 1;
    if(a == NULL) {
	return -1e9;
    }
    if(pos-2 <= q) {
	if(pos-2 < q && ma(a->right) >= sum) {
	    return find(a->right, sum, cSum + cnt(a->left)+1, q);
	}
	if(a->val.F >= sum) {
	    return cSum + cnt(a->left)+1;
	}
	return find(a->left, sum, cSum, q);
    }
    else {
	return find(a->left, sum, cSum, q);
    }
}
void solve() {
    ll sum = getSum(root, n-1, n-1, -1);
    int pos = n-2;
    int ans = 1;
    //cout<<"ASDASD\n";
    //cout<<sum<<'\n';
    //print(root);
    //cout<<endl;
    while(pos >= 0) {
//	cout<<pos<<' ';
	int lo = 0;
	int hi = pos;
	int best = -1;
	best = find(root, sum, 0, pos)-2;
//	cout<<sum<<' '<<pos<<' '<<best<<'\n';

	/*
	while(lo <= hi) {
	    int mid = (lo+hi)/2;
//	    cout<<"lol "<<mid<<' '<<getMax(root, mid, pos, -1)<<' '<<sum<<'\n';
	    if(getMax(root, mid, pos, -1) >= sum) {
		lo = mid+1;
		best = mid;
	    }
	    else {
		hi = mid-1;
	    }
	}
	*/
//	cout<<best<<'\n';
//	cout<<'\n';
	if(best == -1) break;
	sum = getSum(root, best+1, n-1, -1);
	if(getMax(root, best, best, -1) >= sum) {
	    ++ans;
	}
	sum = getSum(root, best, n-1, -1);
	pos = best-1;
    }
    cout<<ans<<'\n';
}
int findPos(Node* k, pair<ll, ll> val) {
    if(k == NULL) {
	return -1e9;
    }
    if(val <= k->val) {
	int q = findPos(k->right, val) + cnt(k->left) + 1;
	if(q < 0) {
	    return cnt(k->left) + 1;
	}
	return q;
    }
    return findPos(k->left, val);
}
void insert(Node*& root, Node * a) {
    int pos = findPos(root, a->val);
    Node * t1, *t2;
    split(root, t1, t2, pos);
    merge(t1, t1, a);
    merge(root, t1, t2);
}
Node * qwe[101010];
int main() {
    cin>>n;
    root = new Node({(ll)1e18, (ll)-1});
    root->prior = -1e18;
    for(int i = 0; i < n; ++i) {
	ll q;
	cin>>q;
	qwe[i] = new Node({(ll)q, i});
	insert(root, qwe[i]);
    }
//	print(root);
//	cout<<endl;;
    solve();
    int m;
    cin>>m;
    for(int i = 0; i< m; ++i) {
	ll k, f;
	cin>>k>>f;
	--k;
	//cout<<"QWEQWE "<<i<<'\n';
	int pos = findPos(root, qwe[k]->val);
	//cout<<pos<<'\n';

	Node * t1, *t2, *t3;
	split(root, t1, t3, pos);
	split(t1, t1, t2, pos-1);

	merge(root, t1, t3);
	qwe[k]->val.F = f;
	insert(root, qwe[k]);

//	print(root);
//	cout<<endl;;
	solve();
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED

Test 66

Verdict: ACCEPTED

Test 67

Verdict: ACCEPTED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: ACCEPTED

Test 70

Verdict: ACCEPTED

Test 71

Verdict: ACCEPTED

Test 72

Verdict: ACCEPTED

Test 73

Verdict: ACCEPTED

Test 74

Verdict: ACCEPTED