Submission #3996472

---

Source Code Expand

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

const int MAXN = 300055;

set<int> PQ;
bitset<MAXN> chk;

int A[MAXN];

int N;

bool f(int i) {
	if(i < 2 || N <= i || i != A[i] || chk[i]) return false;
	return A[i-1] > A[i] && A[i] > A[i+1];
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 2; i < N; i++) if(f(i)) PQ.insert(i);

	for(int x; !PQ.empty();) {
		x = *PQ.begin();
		PQ.erase(PQ.begin());
		swap(A[x-1], A[x+1]);
		chk[x] = true;
		for(int i = x-2; i <= x+2; i++) {
			auto it = PQ.find(i);
			if(PQ.end() != it) PQ.erase(it);
			if(f(i)) PQ.insert(i);
		}
	}

	for(int i = 1; i <= N; i++) if(i != A[i]) {
		puts("No");
		return 0;
	}
	puts("Yes");
	return 0;
}

Submission Info

Judge Result