Youngling tournament

#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 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);
}
void solve() {
    ll sum = getSum(root, n-1, n-1, -1);
    int pos = n-2;
    int ans = 1;
    //cout<<"ASDASD\n";
    //cout<<sum<<'\n';
    while(pos >= 0) {
//	cout<<pos<<' ';
	int lo = 0;
	int hi = pos;
	int best = -1;
	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);
}
void print(Node * a) {
    if(a == NULL) return;
    print(a->left);
    cout<<a->val.F<<' ';
    print(a->right);
}
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: TIME LIMIT EXCEEDED

Test 28

Verdict: TIME LIMIT EXCEEDED

Test 29

Verdict: TIME LIMIT EXCEEDED

Test 30

Verdict: TIME LIMIT EXCEEDED

Test 31

Verdict: TIME LIMIT EXCEEDED

Test 32

Verdict: TIME LIMIT EXCEEDED

Test 33

Verdict: TIME LIMIT EXCEEDED

Test 34

Verdict: TIME LIMIT EXCEEDED

Test 35

Verdict: TIME LIMIT EXCEEDED

Test 36

Verdict: TIME LIMIT EXCEEDED

Test 37

Verdict: TIME LIMIT EXCEEDED

Test 38

Verdict: TIME LIMIT EXCEEDED

Test 39

Verdict: TIME LIMIT EXCEEDED

Test 40

Verdict: TIME LIMIT EXCEEDED

Test 41

Verdict: TIME LIMIT EXCEEDED

Test 42

Verdict: TIME LIMIT EXCEEDED

Test 43

Verdict: TIME LIMIT EXCEEDED

Test 44

Verdict: TIME LIMIT EXCEEDED

Test 45

Verdict: TIME LIMIT EXCEEDED

Test 46

Verdict: TIME LIMIT EXCEEDED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: TIME LIMIT EXCEEDED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: TIME LIMIT EXCEEDED

Test 51

Verdict: TIME LIMIT EXCEEDED

Test 52

Verdict: TIME LIMIT EXCEEDED

Test 53

Verdict: TIME LIMIT EXCEEDED

Test 54

Verdict: TIME LIMIT EXCEEDED

Test 55

Verdict: TIME LIMIT EXCEEDED

Test 56

Verdict: TIME LIMIT EXCEEDED

Test 57

Verdict: TIME LIMIT EXCEEDED

Test 58

Verdict: TIME LIMIT EXCEEDED

Test 59

Verdict: TIME LIMIT EXCEEDED

Test 60

Verdict: TIME LIMIT EXCEEDED

Test 61

Verdict: TIME LIMIT EXCEEDED

Test 62

Verdict: TIME LIMIT EXCEEDED

Test 63

Verdict: TIME LIMIT EXCEEDED

Test 64

Verdict: TIME LIMIT EXCEEDED

Test 65

Verdict: TIME LIMIT EXCEEDED

Test 66

Verdict: TIME LIMIT EXCEEDED

Test 67

Verdict: TIME LIMIT EXCEEDED

Test 68

Verdict: TIME LIMIT EXCEEDED

Test 69

Verdict: TIME LIMIT EXCEEDED

Test 70

Verdict: TIME LIMIT EXCEEDED

Test 71

Verdict: TIME LIMIT EXCEEDED

Test 72

Verdict: TIME LIMIT EXCEEDED

Test 73

Verdict: TIME LIMIT EXCEEDED

Test 74

Verdict: TIME LIMIT EXCEEDED