fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. using namespace std;
  6. typedef pair<int, int> pii;
  7. const int UP = 1, DOWN = 0;
  8. const int INF = 1 << 30;
  9. int N, M;
  10.  
  11. vector<int> inv(vector<int> &a) {
  12.     int sz = a.size();
  13.     vector<int> ret(sz);
  14.     for(int i=0; i<sz; i++) ret[i] = sz - a[i] + 1;
  15.     return ret;
  16. }
  17.  
  18. int calcrun(vector<int> &a) {
  19.     int n = a.size();
  20.     if(n == 1) return 1;
  21.     else {
  22.         int ret = 1;
  23.         bool prev = (a[0] < a[1]);
  24.         for(int i=2; i<n; i++) {
  25.             ret += (prev != (a[i-1] < a[i]));
  26.             prev = (a[i-1] < a[i]);
  27.         }
  28.         return ret;
  29.     }
  30. }
  31.  
  32. vector<int> getLis(vector<int> &p) {
  33.     int n = p.size();
  34.     vector<int> temp(n, INF);
  35.     for(int i=0; i<n; i++) {
  36.         int idx = lower_bound(temp.begin(), temp.end(), p[i]) - temp.begin();
  37.         temp[ idx ] = p[i];
  38.     }
  39.     return temp;
  40. }
  41.  
  42. int getLisSize(vector<int> p) {
  43.     return lower_bound(p.begin(), p.end(), INF) - p.begin();
  44. }
  45.  
  46. vector<pii> makevec(vector<int> &a, int r, bool needsort = false) {
  47.     int n = a.size();
  48.     vector<pii> ret;
  49.     ret.push_back(pii(a[0], r));
  50.     for(int i=1; i<n-1; i++) {
  51.         if((a[i-1] < a[i]) != (a[i] < a[i+1])) {
  52.             r++;
  53.             ret.push_back(pii(a[i], -r));
  54.         }
  55.         else ret.push_back(pii(a[i], r));
  56.     }
  57.     ret.push_back(pii(a[n-1], r));
  58.     if(needsort) sort(ret.begin(), ret.end(), greater<pii>());
  59.     return ret;
  60. }
  61.  
  62. // pattern, q
  63. bool checkvecTwo(vector<pii> &a, vector<pii> &b, int mode) {
  64.     int n = a.size(), m = b.size();
  65.     int arr[] = {3, 2}, val = arr[mode];
  66.     vector<int> s, t, x, y;
  67.     for(int i=0; i<n; i++) {
  68.         if(abs(a[i].second) < val) s.push_back(a[i].first);
  69.         else if(a[i].second != -val) x.push_back(n - a[i].first + 1);
  70.     }
  71.     for(int i=0; i<m; i++) {
  72.         if(abs(b[i].second) < val) t.push_back(b[i].first);
  73.         else if(b[i].second != -val) y.push_back(m - b[i].first + 1);
  74.     }
  75.     int ns = getLisSize( getLis(s) );
  76.     int nt = getLisSize( getLis(t) );
  77.     int nx = getLisSize( getLis(x) );
  78.     int ny = getLisSize( getLis(y) );
  79.     return nt >= ns && ny >= nx;
  80. }
  81.  
  82. // pattern, q
  83. bool checkvecThree(vector<pii> &a, vector<pii> &b) {
  84.     int n = a.size(), m = b.size(), cur = 0;
  85.     vector<int> vp, vq;
  86.     for(int i=0; i<n; i++) {
  87.         vp.push_back(a[i].first);
  88.         int type = a[i].second;
  89.         while(1) {
  90.             bool ok = false;
  91.             if(b[cur].second == type) ok = true;
  92.             if(type < 0 && b[cur].second > 0) {
  93.                 int t = type * (-1);
  94.                 if(b[cur].second == t || b[cur].second == t-1) ok = true;
  95.             }
  96.             if(b[cur].second < 0 && type > 0) {
  97.                 int t = b[cur].second * (-1);
  98.                 if(type == t || type == t-1) ok = true;
  99.             }
  100.             if(ok) {
  101.                 vq.push_back(b[cur].first);
  102.                 cur++; break;
  103.             }
  104.             if(++cur >= m) return false;
  105.         }
  106.     }
  107.     return true;
  108. }
  109.  
  110. bool solve_1(vector<int> &p, vector<int> &q) {
  111.     int n = getLisSize( getLis(p) );
  112.     int m = getLisSize( getLis(q) );
  113.     return m >= n;
  114. }
  115.  
  116. bool solve_2(vector<int> &p, vector<int> &q) {
  117.     vector<pii> vp, vq;
  118.     if(q[0] > q[1]) {
  119.         vp = makevec(p, 2), vq = makevec(q, 1);
  120.         return checkvecTwo(vp, vq, 0);
  121.     }
  122.     else {
  123.         vp = makevec(p, 1), vq = makevec(q, 1);
  124.         return checkvecTwo(vp, vq, 1);
  125.     }
  126. }
  127.  
  128. bool solve_3(vector<int> &p, vector<int> &q) {
  129.     if(q[0] > q[1]) return false;
  130.     vector<pii> vp, vq;
  131.     vp = makevec(p, 1, true); vq = makevec(q, 1, true);
  132.     return checkvecThree(vp, vq);
  133. }
  134.  
  135. int main() {
  136.     cin >> N;
  137.     vector<int> q(N);
  138.     for(int i=0; i<N; i++) scanf("%d", &q[i]);
  139.  
  140.     cin >> M;
  141.     vector<int> pat(M);
  142.     for(int i=0; i<M; i++) scanf("%d", &pat[i]);
  143.  
  144.     if(M > 1 && pat[0] > pat[1]) {
  145.         q   = inv(q  );
  146.         pat = inv(pat);
  147.     }
  148.  
  149.     int RUN = calcrun(pat);
  150.     if      (RUN == 1)  cout << (solve_1(pat, q) ? "Yes" : "No") << endl;
  151.     else if (RUN == 2)  cout << (solve_2(pat, q) ? "Yes" : "No") << endl;
  152.     else if (RUN == 3)  cout << (solve_3(pat, q) ? "Yes" : "No") << endl;
  153.     else                cout << "No" << endl;
  154.     return 0;
  155. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
5
3 4 2 1 5
3
1 2 3
stdout
copy 
Yes
https://ideone.com/hocAVt
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!