fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4. const int UP = 1, DOWN = 0;
  5. const int INF = 1 << 30;
  6. int n, m;
  7.  
  8. vector<int> inv(vector<int> a) {
  9.     int sz = a.size();
  10.     vector<int> ret(sz);
  11.     for(int i=0; i<sz; i++) ret[i] = sz - a[i] + 1;
  12.     return ret;
  13. }
  14.  
  15. vector<pii> getrun(vector<int> a) {
  16.     vector<pii> ret;
  17.     if(a.size() == 1) {
  18.         ret.push_back(pii(0, UP));
  19.         return ret;
  20.     }
  21.  
  22.     if(a[0] < a[1]) ret.push_back(pii(0, UP  ));
  23.     if(a[0] > a[1]) ret.push_back(pii(0, DOWN));
  24.  
  25.     for(size_t i=1; i<a.size()-1; i++) {
  26.         if(a[i-1] < a[i] && a[i] > a[i+1])
  27.             ret.push_back(pii(i, DOWN));
  28.         if(a[i-1] > a[i] && a[i] < a[i+1])
  29.             ret.push_back(pii(i, UP  ));
  30.     }
  31.     return ret;
  32. }
  33.  
  34. pii getedge(vector<int> a, vector<pii> run) {
  35.     int n = a.size();
  36.     int x = run[1].first, y = run[2].first;
  37.     int ret_a = upper_bound(a.begin(), a.begin()+x, a[y]) - a.begin();
  38.     int ret_b = upper_bound(a.begin()+y, a.begin()+n, a[x]) - a.begin();
  39.     ret_b = n - ret_b;
  40.     return pii(ret_a, ret_b);
  41. }
  42.  
  43. int solve_1(vector<int> a) {
  44.     int x = a.size(), ret = 0;
  45.     vector<int> temp(x, (int)1e9);
  46.     for(int i=0; i<x; i++) {
  47.         int idx = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin();
  48.         temp[ idx ] = a[i];
  49.         ret = max(ret, idx+1);
  50.     }
  51.     return ret;
  52. }
  53.  
  54. bool solve_2(int sz, vector<int> p, vector<int> q, vector<pii> run_p, vector<pii> run_q) {
  55.     int n = q.size(), m = p.size();
  56.     vector<pii> vp, vq;
  57.     run_p.push_back(pii(INF, -1));
  58.     run_q.push_back(pii(INF, -1));
  59.  
  60.     for(int i=0; i<n; i++) {
  61.         for(int j=1; j<=sz; j++) {
  62.             if(i < run_q[j].first) {
  63.                 vq.push_back(pii(q[i], j-1));
  64.                 break;
  65.             }
  66.             else if(i == run_q[j].first) break;
  67.         }
  68.     }
  69.     for(int i=0; i<m; i++) {
  70.         for(int j=1; j<=sz; j++) {
  71.             if(i < run_p[j].first) {
  72.                 vp.push_back(pii(p[i], j-1));
  73.                 break;
  74.             }
  75.             else if(i == run_p[j].first) break;
  76.         }
  77.     }
  78.     sort(vp.begin(), vp.end(), greater<pii>());
  79.     sort(vq.begin(), vq.end(), greater<pii>());
  80.  
  81.     int cur = 0, prev = (int)1e9;
  82.     for(size_t i=0; i<vp.size(); i++) {
  83.         int type = vp[i].second;
  84.         while(1) {
  85.             if(vq[cur].second == type && vq[cur].first < prev) {
  86.                 prev = vq[cur++].first;
  87.                 break;
  88.             }
  89.             if(++cur >= (int)vq.size()) return false;
  90.         }
  91.     }
  92.     return true;
  93. }
  94.  
  95. int main() {
  96.     cin >> n;
  97.     vector<int> q(n);
  98.     for(int i=0; i<n; i++) cin >> q[i];
  99.  
  100.     cin >> m;
  101.     vector<int> pat(m);
  102.     for(int i=0; i<m; i++) cin >> pat[i];
  103.  
  104.     if(m > 1 && pat[0] > pat[1]) {
  105.         q   = inv(q  );
  106.         pat = inv(pat);
  107.     }
  108.  
  109.     vector<pii> run_q   = getrun(q  );
  110.     vector<pii> run_pat = getrun(pat);
  111.  
  112.     int pat_sz = run_pat.size(), flag = pat.size();
  113.     if(pat_sz > (int)run_q.size()) {
  114.         cout << "No" << endl;
  115.     }
  116.     else if(pat_sz == 1) {
  117.         int l = solve_1(q);
  118.         if(l >= flag) cout << "Yes" << endl;
  119.         else cout << "No" << endl;
  120.     }
  121.     else if(pat_sz == 2) {
  122.         // pat は必ず山形である
  123.         if(run_q[1].second == DOWN) {
  124.             if(solve_2(2, pat, q, run_pat, run_q)) cout << "Yes" << endl;
  125.             else cout << "No" << endl;
  126.         }
  127.         else cout << "No" << endl;
  128.     }
  129.     else if(pat_sz == 3) {
  130.         // pat は必ず 山 -> 谷 である
  131.         if(run_q[1].second == DOWN) {
  132.             pii eq = getedge(q, run_q);
  133.             pii ep = getedge(pat, run_pat);
  134.             if(eq < ep) cout << "No" << endl;
  135.             else {
  136.                 if(solve_2(3, pat, q, run_pat, run_q)) cout << "Yes" << endl;
  137.                 else cout << "No" << endl;
  138.             }
  139.         }
  140.         else cout << "No" << endl;
  141.     }
  142.     else cout << "No" << endl;
  143.     return 0;
  144. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
5
3 4 2 1 5
3
1 2 3
stdout
copy 
Yes
https://ideone.com/v5H4vf
language:
C++ (gcc 8.3)
created:
7 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!