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