Submission #1025379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025379		vjudge1	Martian DNA (BOI18_dna)	C++17	0 / 100	418 ms	22916 KiB

dna

#include <bits/stdc++.h>
typedef long double ld;
#define int long long
#define TC int t; cin >> t; for(int _=1; _<=t; _++)
#define bismillah ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
using namespace std;

const int N = 2e5+7, INF = 1e18;

int a[N];
int n, k, q;
map<int, int> mapp, frq;

signed main(){
   bismillah;
   cin >> n >> k >> q;
   for(int i=1; i<=n; i++){
      cin >> a[i];
      frq[a[i]]++;
      mapp[a[i]] = INF;
   }

   int done = k;
   while(q--){
      int x, c; cin >> x >> c;
      mapp[x] = c; done--;

      if(frq[x]<c){
         cout << "impossible";
         return 0;
      }
   }

   map<int, int> now;
   map<int, bool> flag;
   int ans = n;
   int l = 1; // l==r allowed

   // find prefix first
   int r = 1;
   for(int i=1; i<=n; i++){
      now[a[i]]++;
      if(now[a[i]]>=mapp[a[i]] && !flag[a[i]]){
         done++;
         flag[a[i]] = 1;
      }

      if(done==k){
         ans = min(ans, i-l+1);
         r = i;
         break;
      }
   }

   for(;r<=n; r++){
      if(done==k){
         while(now[a[l]]>mapp[a[l]]){
            now[a[l]]--;
            l++;
         }
         ans = min(ans, r-l+1);
         //cout << l << " " << r << '\n';
      }

      now[a[r]]++;
      if(now[a[r]]>=mapp[a[r]] && !flag[a[r]]){
         done++;
         flag[a[r]] = 1;
      }

      now[a[l]]--;
      if(now[a[l]]<mapp[a[l]] && flag[a[l]]){
         done--;
         flag[a[l]] = 0;
      }l++;
   }

   if(done==k){ // last check
      while(now[a[l]]>mapp[a[l]]){
         now[a[l]]--;
         l++;
      }
      ans = min(ans, r-l+1);
      //cout << l << " " << r << '\n';
   }

   cout << ans;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32