Submission #1655298

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true

typedef long long ll;
typedef pair<int, int> ii;

struct NODE{
  int num;
  int a;
  bool operator<(const NODE r){
    if(a != r.a) return a < r.a;
    else return num < r.num;
  }
};

int main(){

	int n;
  cin >> n;
  vector<NODE> v(n);
  rep(i ,n) {
    v[i].num = i;
    cin >> v[i].a;
  }

  SORT(v);

  int ans = (v[n-1].num == 0 ? 0 : 1);
  int pos = -1;
  REP(i, 0, n){
    int maxi = -1;
    if(v[i].num < pos){
      ans++;
      int j;
      for(j = i; v[i].a == v[j].a; j++){
        if(v[j].num < pos) maxi = max(maxi, v[j].num);
      }
      i = j-1;
      pos = maxi;
    }
    else pos = v[i].num;
  }

  cout << ans << endl;

	return 0;
}

Submission Info

Judge Result