Submission #3998119

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
void fuk() { puts("No"); exit(0); }

const int MAXN = 300055;

int A[MAXN], B[MAXN];

int N;

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

	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		if(i != A[i]) B[i] = i < A[i] ? 1 : -1;
	}

	for(int s = 1, e; s <= N;) {
		if(B[s]) {
			if(s == N || B[s+1]) fuk();
			e = s+1;
		} else e = s;
		for(; e < N && (!!B[e]) != (!!B[e+1]); e++);
		int mn = N+1, mx = -1;
		for(int i = s; i <= e; i++) {
			if(A[i] < mn) mn = A[i];
			if(mx < A[i]) mx = A[i];
		}
		if(mx != e || mn != s) fuk();
		mn = mx = -1;
		for(int i = s; i <= e; i++) {
			if(B[i] > 0) {
				if(A[i] < mx) fuk();
				mx = A[i];
			} else if(B[i] < 0) {
				if(A[i] < mn) fuk();
				mn = A[i];
			}
		}
		s = e+1;
	}

	puts("Yes");
	return 0;
}

Submission Info

Judge Result