oj.uz

Submission #1009816

# Submission time Handle Problem Language Result Execution time Memory
1009816 2024-06-28T06:03:56 Z kebine Martian DNA (BOI18_dna) C++17
0 / 100
 313 ms 22468 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define inf LLONG_MAX
#define pb push_back
#define lc 2*pos+1
#define rc 2*pos+2
#define halleluya  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
signed main(){
halleluya
    int n,k,re;cin>>n>>k>>re;
    int num[n];
    map<int,int>req;
    map<int,int>freq;
    vector<int>jum;
    int tot=re;
    map<int,int>ad;
    for (int i=0;i<n;i++)cin>>num[i];    
    while (re--){
        int x,y;cin>>x>>y;
        ad[x]=1;
        req[x]=y;
        jum.pb(x);
    }

    // for (int i=0;i<n;i++){
    //     for (auto x:jum) {
    //         if (0<i) freq[{i,x}]=freq[{i-1,x}];
    //         if (x==num[i]) freq[{i,x}]++;
    //     }
    // }
    int l=0,r=0;
    freq[num[0]]++;
    map<int,bool>vis;
    int ben=0;

    int ans=inf;
    while(l<=r && r<n){
        bool sal=1;
        while (ben<tot && r+1<n){
            r++;
            freq[num[r]]++;
            if (ad[num[r]]){
            if (freq[num[r]]>=req[num[r]] && vis[num[r]]==0 ){
                vis[num[r]]=1;
                // cout<<"namben "<<num[r]<<" di "<<r<<endl;
                ben++;
            } 
            }
        }
        while (ben>=tot && l<=r && l+1<n){
            ans=min(ans,r-l+1);
            // cout<<freq[num[l]]<<endl;
            freq[num[l]]--;
            if (ad[num[l]]){
                // cout<<l<<" "<<r<<" "<<" "<<freq[num[l]]<<" "<<req[num[l]] <<" "<<vis[num[l]]<<" "<<ben<<" ";
                if (freq[num[l]]<req[num[l]] && vis[num[l]]){
                vis[num[l]]=0;
                ben--;
            }
            // cout<<ben<<endl;
            }
            l++;

        } 
        r++; 
        }
        
    if (ans==inf)cout<<"impossible";
    else cout<<ans;
}

// impossible -> jumlah kurang atau emang gaada substringnya 
// harus consecutive
// constraint r 
// cuman perlu shortest
// sliding window?
// cuma save jumlah k 
// n*k

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:41:14: warning: unused variable 'sal' [-Wunused-variable]
   41 |         bool sal=1;
      |              ^~~

Subtask #1
0 / 16.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 32.0

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