fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int N; 
  8.     if(!(cin >> N)) return 0;
  9.     vector<long long> L(N), R(N);
  10.     for (int i = 0; i < N; ++i) cin >> L[i] >> R[i];
  11.     int M; cin >> M;
  12.     vector<long long> A(M+1);
  13.     for (int i = 1; i <= M; ++i) cin >> A[i];
  14.  
  15.     // sort by L and build prefix max of R
  16.     vector<pair<long long,long long>> seg(N);
  17.     for(int i=0;i<N;++i) seg[i]={L[i],R[i]};
  18.     sort(seg.begin(), seg.end());
  19.     vector<long long> Ls(N), prefMaxR(N);
  20.     for (int i=0;i<N;++i){
  21.         Ls[i]=seg[i].first;
  22.         prefMaxR[i]=seg[i].second;
  23.         if(i) prefMaxR[i]=max(prefMaxR[i], prefMaxR[i-1]);
  24.     }
  25.     auto bestR = [&](long long x)->long long{
  26.         int idx = upper_bound(Ls.begin(), Ls.end(), x) - Ls.begin() - 1;
  27.         if (idx < 0) return LLONG_MIN/4; // không có L <= x
  28.         return prefMaxR[idx];
  29.     };
  30.  
  31.     // two pointers + deques for min/max
  32.     deque<pair<long long,int>> dqMin, dqMax;
  33.     auto add = [&](int idx){
  34.         long long v=A[idx];
  35.         while(!dqMin.empty() && dqMin.back().first>=v) dqMin.pop_back();
  36.         dqMin.emplace_back(v, idx);
  37.         while(!dqMax.empty() && dqMax.back().first<=v) dqMax.pop_back();
  38.         dqMax.emplace_back(v, idx);
  39.     };
  40.     auto eraseIdx = [&](int idx){
  41.         if(!dqMin.empty() && dqMin.front().second==idx) dqMin.pop_front();
  42.         if(!dqMax.empty() && dqMax.front().second==idx) dqMax.pop_front();
  43.     };
  44.  
  45.     int r=0;
  46.     vector<int> far(M+2, 0);
  47.     for(int l=1; l<=M; ++l){
  48.         while(r+1<=M){
  49.             add(r+1);
  50.             long long mn=dqMin.front().first;
  51.             long long mx=dqMax.front().first;
  52.             if(mx <= bestR(mn)) ++r;               // vẫn hợp lệ, mở rộng
  53.             else {                                  // không hợp lệ, hoàn tác
  54.                 eraseIdx(r+1);
  55.                 break;
  56.             }
  57.         }
  58.         far[l]=r;
  59.         eraseIdx(l);
  60.     }
  61.  
  62.     int segments = 0;
  63.     int pos = 1;
  64.     while(pos <= M){
  65.         if(far[pos] < pos){ cout << -1 << '\n'; return 0; }
  66.         ++segments;
  67.         pos = far[pos] + 1;
  68.     }
  69.     cout << (segments - 1) << '\n'; // số lần đổi nguyên liệu
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5
2 5
6 8
9 12
13 15
16 18
7
2 3 6 8 9 14 17
stdout 
4
https://ideone.com/vE3d4O
language:
C++14 (gcc 8.3)
created:
12 hours 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!