oj.uz

Submission #1025379

# Submission time Handle Problem Language Result Execution time Memory
1025379 2024-07-17T01:09:03 Z vjudge1 Martian DNA (BOI18_dna) C++17
0 / 100
 418 ms 22916 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 418 ms 22916 KB Output isn't correct
2 Halted 0 ms 0 KB -