#include<cstdio> #include<cmath> #include<vector> #include<iostream> #include<string> #include<algorithm> using namespace std; int main(){ int n; int to_remove = 1; int last_removed = 0; int res = 0; int c; scanf("%d", &n); int l = 1; int r = n; vector<int> ord(n+1); vector<int> org(n+1); vector<int> removed(n+1); for(int i=1; i <n + 1; i++){ scanf("%d", &org[i]); ord[org[i]] = i; } while(to_remove < n){ int maxl = l - 1; int minr = r + 1; // pierwszy do wyrzucenia za n int max_number = to_remove; for( int i = last_removed + 1; i <= to_remove; i++){ if (ord[i] < ord[n] && maxl < ord[i]) maxl = ord[i]; if (ord[i] > ord[n] && minr > ord[i]) minr = ord[i]; } if ( minr == r + 1 && maxl == l - 1){ res++; to_remove++; } else{ if(maxl >= l) to_remove = max(*max_element(org.begin() + l, org.begin() + maxl + 1), to_remove); if (minr <= r) to_remove = max(*max_element(org.begin() + minr, org.begin() + r + 1 ), to_remove); l = maxl + 1; r = minr - 1; last_removed = to_remove; } } cout << 1 + 2 * n << " " <<res << endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include<cstdio> #include<cmath> #include<vector> #include<iostream> #include<string> #include<algorithm> using namespace std; int main(){ int n; int to_remove = 1; int last_removed = 0; int res = 0; int c; scanf("%d", &n); int l = 1; int r = n; vector<int> ord(n+1); vector<int> org(n+1); vector<int> removed(n+1); for(int i=1; i <n + 1; i++){ scanf("%d", &org[i]); ord[org[i]] = i; } while(to_remove < n){ int maxl = l - 1; int minr = r + 1; // pierwszy do wyrzucenia za n int max_number = to_remove; for( int i = last_removed + 1; i <= to_remove; i++){ if (ord[i] < ord[n] && maxl < ord[i]) maxl = ord[i]; if (ord[i] > ord[n] && minr > ord[i]) minr = ord[i]; } if ( minr == r + 1 && maxl == l - 1){ res++; to_remove++; } else{ if(maxl >= l) to_remove = max(*max_element(org.begin() + l, org.begin() + maxl + 1), to_remove); if (minr <= r) to_remove = max(*max_element(org.begin() + minr, org.begin() + r + 1 ), to_remove); l = maxl + 1; r = minr - 1; last_removed = to_remove; } } cout << 1 + 2 * n << " " <<res << endl; return 0; } |