Youngling tournament

#include <iostream>
#include <set>
#include <unordered_map>
#define SZ (1<<19)
using namespace std;
int N, M;

long long sp[SZ];

void putv(int a, long long v){a+=SZ/2;
  sp[a]+=v;
  for (a/=2; a; a/=2){
    sp[a]=sp[2*a]+sp[2*a+1];
  }
}
long long gets(int a, int b){a+=SZ/2; b+=SZ/2;
  long long rv=0;
  while (a<b){
    if (a%2==1) rv+=sp[a++];
    if (b%2==0) rv+=sp[b--];
    a/=2; b/=2;
  }if (a==b) rv+=sp[a];
  return rv;
}


set<long long> luvut;
unordered_map<long long, int> ix;
long long li[202020];




multiset<long long> p;
multiset<long long>::iterator it;

int v(){
  if (N==1) return 1;
  
  int ans=2;
  long long mns=0;
  it=p.begin();
  mns+=*it;
  ++it;
  mns+=*it;
  
  while (1){
    it=p.lower_bound(mns);
    if (it==p.end()) break;
    mns=gets(0, ix[*it]-1);
    if (*it>=mns) ++ans;
    mns+=*it;
  }
  return ans;
}


long long f[202020];
int k[202020];
long long f2[202020];

int main(){
  cin >> N;
  luvut.insert(-1);
  for (int i=0; i<N; ++i){
    cin >> f[i];
    luvut.insert(f[i]);
    p.insert(f[i]);
  }
  cin >> M;
  for (int i=0; i<M; ++i){
    cin >> k[i] >> f2[i]; --k[i];
    luvut.insert(f2[i]);
  }
  int ii=0;
  for (auto a:luvut){
    ix[a]=ii;
    li[ii]=a;
    ++ii;
  }
  for (int i=0; i<N; ++i) putv(ix[f[i]], f[i]);
  cout << v() << "\n";
  for (int i=0; i<M; ++i){
    p.erase(p.find(f[k[i]]));
    putv(ix[f[k[i]]], -f[k[i]]);
    f[k[i]]=f2[i];
    p.insert(f[k[i]]);
    putv(ix[f[k[i]]], f[k[i]]);
    cout << v() << "\n";
  }
  
}

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