Advertisement
Josif_tepe

Untitled

Feb 6th, 2023
573
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5.  
  6.  
  7.  
  8. int main()
  9. {
  10.     ios_base::sync_with_stdio(false);
  11.     int n, k;
  12.     cin>>n >> k;
  13.     int m;
  14.     cin>>m;
  15.  
  16.     vector<int> req(k + 1, 0);
  17.    
  18.     vector<int>v;
  19.    
  20.     for(int i=0; i<n; i++){
  21.         int a;
  22.         cin>>a;
  23.         v.push_back(a);
  24.     }
  25.     for(int j=0; j<m; j++){
  26.     int a, b;
  27.     cin>>a>>b;
  28.     req[a] = b;
  29.     }
  30.    
  31.    
  32.     int min_length=2e9;
  33.     int tmp = m;
  34.     int j = 0;
  35.     for(int i = 0; i < n; i++) {
  36.         while(tmp > 0 and j < n) {
  37.             req[v[j]]--;
  38.             if(req[v[j]] == 0) {
  39.                 tmp--;
  40.             }
  41.             j++;
  42.         }
  43.        
  44.         if(tmp == 0) {
  45.             min_length = min(min_length, j - i);
  46.         }
  47.         req[v[i]]++;
  48.        
  49.         if(req[v[i]] > 0) {
  50.             tmp++;
  51.         }
  52.     }
  53.    
  54.  
  55.     if(min_length == 2e9) {
  56.         cout << "impossible";
  57.     }
  58.     else
  59.     cout << min_length  << endl;
  60.     return 0;
  61. }
  62. /*
  63.  5 2 2
  64.  0 1 1 0 1
  65.  0 1
  66. 1 1
  67.  
  68.  13 4 3
  69.  1 1 3 2 0 1 2 0 0 0 0 3 1
  70.  0 2
  71.  2 1
  72.  1 2
  73.  
  74.  5 3 1
  75.  1 2 0 1 2
  76.  0 2
  77.  **/
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement