Submission #1083358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083358		XecovZ	Martian DNA (BOI18_dna)	C++17	100 / 100	664 ms	50144 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 st = 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);
         st = i;
         break;
      }
   }

   int r;
   for(r=st; r<=n; r++){
      if(r>st){
         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){
         while(l<r && (now[a[l]]>mapp[a[l]] || !flag[a[l]])){
            now[a[l]]--;
            l++;
         }
         ans = min(ans, r-l+1);
         /* cout << l << " " << r << '\n';
         break; */
      }
   }
   

   cout << ans;
}
/* 
18 4 3
0 3 0 1 3 1 2 0 0 1 1 2 0 0 1 3 1 2
0 2
1 2
2 1
 */

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