Money

input/code.cpp: In function 'int add(int)':
input/code.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 1010101
int n;
int v[N];
int bit[N];

void a(int k, int x) {
  for (; k <= N; bit[k] += x, k += k&-k);
}

int upto(int k) {
  int s = 0;
  for (; k >= 1; s += bit[k], k -= k&-k);
  return s;
}

int sumq(int a, int b) {
  return upto(b) - upto(a-1);
}

vector<vector<int>> chain;
set<int> cur;

int beg() { return *(cur.begin()); }
int e() { return *(cur.rbegin()); }
int add(int x) {
  cur.insert(x);
}

bool between(int a, int b) {
  if (abs(b-a) < 2) return false;
  return sumq(a+1, b-1) > 0;
}

void dmp() {
  for (int v : cur) {
    a(v, 1);
  }
}

int ans;

int main() {
  IO; cin>>n;
  FOR(i,0,n) cin>>v[i];


  FOR(i,0,n) {
    if (!cur.size()) {
      add(v[i]);
      continue;
    }

    // cur has something
    int x = v[i];

    if (x < e()) {
      // x is too small
      dmp();
      cur.clear();
      add(v[i]);
      ans++;
      continue;
    }

    // find if a < m exists
    int big = max(e(), x);
    int small = min(x, beg());

    if (between(small, big)) {
      // x can't be included.
      dmp();
      cur.clear();
      add(x);
      ans++;
      continue;
    }

    // okay to add x.
    add(x);
  }

  if (cur.size() > 0) ans++;
  cout<<ans<<"\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 3

Verdict: ACCEPTED

Test 28

Group: 3

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 3

Verdict: ACCEPTED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: ACCEPTED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: ACCEPTED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 4

Verdict: ACCEPTED

Test 40

Group: 4

Verdict: ACCEPTED

Test 41

Group: 4

Verdict: ACCEPTED

Test 42

Group: 4

Verdict: ACCEPTED

Test 43

Group: 4

Verdict: ACCEPTED

Test 44

Group: 4

Verdict: ACCEPTED

Test 45

Group: 4

Verdict: ACCEPTED

Test 46

Group: 4

Verdict: ACCEPTED

Test 47

Group: 4

Verdict: ACCEPTED

Test 48

Group: 4

Verdict: ACCEPTED

Test 49

Group: 4

Verdict: ACCEPTED

Test 50

Group: 4

Verdict: ACCEPTED

Test 51

Group: 4

Verdict: ACCEPTED

Test 52

Group: 4

Verdict: ACCEPTED

Test 53

Group: 4

Verdict: ACCEPTED

Test 54

Group: 4

Verdict: ACCEPTED

Test 55

Group: 4

Verdict: ACCEPTED

Test 56

Group: 4

Verdict: ACCEPTED

Test 57

Group: 4

Verdict: ACCEPTED

Test 58

Group: 4

Verdict: ACCEPTED

Test 59

Group: 4

Verdict: ACCEPTED

Test 60

Group: 4

Verdict: ACCEPTED

Test 61

Group: 4

Verdict: ACCEPTED

Test 62

Group: 4

Verdict: ACCEPTED