Submission #1172977

---

Source Code Expand

#include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>

#define rep(i,n) for(int i=0; i<int(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

vector<int> A[100010];

int main() {
	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		A[x].push_back(i);
	}

	int ans = 0;
	int pos = 100010;
	int i,j;

	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < A[i].size(); j++)
			printf("%2d",A[i][j]);
	}
	printf("\n");

	for (i = 0; i < 100010; i++) {
		if (A[i].size()) {
			for (j = 0; j < A[i].size(); j++)
				if (A[i][j] > pos) break;
			if (j == 0)
				pos = A[i].back(); //前の位置
			else {
				ans++;
				pos = A[i][j - 1]; //前の位置
			}
		}
	}
		if (pos == 0)ans--;  //最後の位置がNだったら1引く
		cout << ans << endl;
	return 0;
}

Submission Info

Judge Result