fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7.  
  8. void solve() {
  9.     ll n;
  10.     cin >> n;
  11.     vector <ll> l1(n);
  12.     vector <ll> maxpos(n+1, -1), minpos(n+1, inf);
  13.     for (ll i = 0; i < n; i++){
  14.         cin >> l1[i];
  15.         maxpos[l1[i]] = max(i, maxpos[l1[i]]);
  16.         minpos[l1[i]] = min(i, minpos[l1[i]]);
  17.     }
  18.     auto l2 = l1;
  19.     sort(l2.begin(), l2.end());
  20.     if (l1.size() == 1 || l2[0] % 2 != l2[n-1] % 2){
  21.         cout << "YES" << "\n";
  22.         return;
  23.     }
  24.     ll min_pos = inf;
  25.     ll max_pos = inf;
  26.     for (int i = 0; i < n; i++){
  27.         if (l2[i] % 2 != l2[0] % 2){
  28.             min_pos = l2[i]; break;
  29.         }
  30.     }
  31.     for (int i = n-1; i>= 0; i--){
  32.         if (l2[i] % 2 != l2[0] % 2){
  33.             max_pos = l2[i]; break; 
  34.         }
  35.     }
  36.     // cout << min_pos << " " << max_pos << "\n";
  37.     if (min_pos == inf){
  38.         if (l1 == l2){
  39.             cout << "YES" << "\n";
  40.         }
  41.         else{
  42.             cout << "NO" << "\n";
  43.         }
  44.         return;
  45.     }
  46.     ll v1 = -1; ll v2 = inf;
  47.     for (int i = 1; i < min_pos; i++){
  48.         v1 = max(v1, maxpos[i]);
  49.     }
  50.     for (int i = n; i > max_pos; i--){
  51.         v2 = min(v2, minpos[i]);
  52.     }
  53.     if (v1 > v2){
  54.         cout << "NO" << "\n";
  55.     }
  56.     else{
  57.         cout << "YES" << "\n";
  58.     }
  59. }
  60.  
  61. int main() {
  62.     ios::sync_with_stdio(false);
  63.     cin.tie(nullptr);
  64.  
  65.     ll t = 1;
  66.     cin >> t;
  67.     while (t--) {
  68.         solve();
  69.     }
  70.  
  71.     return 0;
  72. }
Runtime error #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/TnlYto
language:
C++14 (clang 8.0)
created:
2 hours ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!