oj.uz

답안 #948193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948193 2024-03-17T20:21:02 Z NourWael Martian DNA (BOI18_dna) C++17
0 / 100
 43 ms 6744 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std; 
int req[200005];
int freq[200005];
int a[200005];


signed main() {
 
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

    int n,k,rq; cin>>n>>k>>rq;
    for(int i=0; i<n; i++) cin>>a[i];
    
    for(int i=0; i<rq; i++) {
      int x,c; cin>>x>>c;
      req[x] = c;
    }

    int l = 1, r = n, ans = -1;
    while(l<=r) {
      int mid = (l+r)/2;
      int cnt = 0;

      for(int i=0; i<mid; i++) {
         freq[a[i]]++;
         if(req[a[i]] && freq[a[i]]==req[a[i]]) cnt++; 
      }
     
      bool f = 0;
      int ind = 0;
      for(int i=mid; i<n; i++) {
         if(cnt==rq) { f = 1; break; }
         if(req[a[ind]] && freq[a[ind]]==req[a[ind]]) cnt--; 
         freq[a[ind]]--, freq[a[i]]++;
         if(req[a[i]] && freq[a[i]]==req[a[i]]) cnt++; 
         ind++;
      }
      if(cnt==rq) f = 1;
      
      if(f) { r = mid-1; ans = mid; }
      else l = mid+1;
      for(int i=0; i<=k; i++) freq[i]=0;
    }

    if(ans==-1) cout<<"IMPOSSIBLE";
    else cout<<ans;
   return 0;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2508 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2548 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Incorrect 1 ms 2396 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 4956 KB Output is correct
2 Correct 20 ms 5148 KB Output is correct
3 Correct 12 ms 4952 KB Output is correct
4 Correct 14 ms 4956 KB Output is correct
5 Correct 21 ms 5712 KB Output is correct
6 Correct 15 ms 4956 KB Output is correct
7 Incorrect 19 ms 5212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 6480 KB Output is correct
2 Correct 32 ms 6264 KB Output is correct
3 Correct 27 ms 5980 KB Output is correct
4 Correct 9 ms 4952 KB Output is correct
5 Incorrect 43 ms 6744 KB Output isn't correct
6 Halted 0 ms 0 KB -