Submission #931329

#	Time	Username	Problem	Language	Result	Execution time	Memory
931329		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	210 ms	17760 KiB

dna

/*
                              _,add8ba,
                            ,d888888888b,
                           d8888888888888b                        _,ad8ba,_
                          d888888888888888)                     ,d888888888b,
                          I8888888888888888 _________          ,8888888888888b
                __________`Y88888888888888P"""""""""""baaa,__ ,888888888888888,
            ,adP"""""""""""9888888888P""^                 ^""Y8888888888888888I
         ,a8"^           ,d888P"888P^                           ^"Y8888888888P'
       ,a8^            ,d8888'                                     ^Y8888888P'
      a88'           ,d8888P'                                        I88P"^
    ,d88'           d88888P'                                          "b,
   ,d88'           d888888'                                            `b,
  ,d88'           d888888I                                              `b,
  d88I           ,8888888'            ___                                `b,
 ,888'           d8888888          ,d88888b,              ____            `b,
 d888           ,8888888I         d88888888b,           ,d8888b,           `b
,8888           I8888888I        d8888888888I          ,88888888b           8,
I8888           88888888b       d88888888888'          8888888888b          8I
d8886           888888888       Y888888888P'           Y8888888888,        ,8b
88888b          I88888888b      `Y8888888^             `Y888888888I        d88,
Y88888b         `888888888b,      `""""^                `Y8888888P'       d888I
`888888b         88888888888b,                           `Y8888P^        d88888
 Y888888b       ,8888888888888ba,_          _______        `""^        ,d888888
 I8888888b,    ,888888888888888888ba,_     d88888888b               ,ad8888888I
 `888888888b,  I8888888888888888888888b,    ^"Y888Y"^      ____.,ad88888888888I
  88888888888b,`888888888888888888888888b,     ""      ad888888888888888888888'
  8888888888888698888888888888888888888888b_,ad88ba,_,d88888888888888888888888
  88888888888888888888888888888888888888888b,`""""" d8888888888888888888888888I
  8888888888888888888888888888888888888888888baaad888888888888888888888888888'
  Y8888888888888888888888888888888888888888888888888888888888888888888888888P
  I888888888888888888888888888888888888888888888P^  ^Y8888888888888888888888'
  `Y88888888888888888P88888888888888888888888888'     ^88888888888888888888I
   `Y8888888888888888 `8888888888888888888888888       8888888888888888888P'
    `Y888888888888888  `888888888888888888888888,     ,888888888888888888P'
     `Y88888888888888b  `88888888888888888888888I     I888888888888888888'
       "Y8888888888888b  `8888888888888888888888I     I88888888888888888'
         "Y88888888888P   `888888888888888888888b     d8888888888888888'
            ^""""""""^     `Y88888888888888888888,    888888888888888P'
                             "8888888888888888888b,   Y888888888888P^
                              `Y888888888888888888b   `Y8888888P"^
                                "Y8888888888888888P     `""""^
                                  `"YY88888888888P'
                                       ^""""""""'
*Allah is watching me :) * 
*/
 
#include<bits/stdc++.h>
#define ll            long long	
#define yes           "YES\n"
#define no            "NO\n"
#define all(v)        v.begin(), v.end()
#define pb            push_back
#define F             first
#define S             second
#define mk            make_pair
#define skip          continue;
#define ld            long double
using namespace std;
const int e=1e9+11;	
const int L=1e7+11;
const int N=2e5+11;
const ll inf=1e18;
const int mod=1e9+7;
void solve(){
	int n,k,d;
	cin>>n>>k>>d;
	int a[n+1];
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	map<int,int>mp,had;
	int ans=INT_MAX;
	for(int i=1; i<=d; i++){
		int u,v;
		cin>>u>>v;
		had[u]=1;
		mp[u]=v;
	}
	int l=1,r=1,c=d;
	while(r<=n){
		int v=a[r];
		mp[v]--;
		if(mp[v]==0){
			c--;
			if(c==0){
				while((mp[a[l]]+1<=0 || !had[a[l]]) && l<=r){
					if(had[a[l]]){
						mp[a[l]]++;
					}
					l++;
				}
				ans=min(ans,r-l+1);
				mp[a[l]]++;
				if(mp[a[l]]>0){
					c++;
				}
				l++;
			}
		}
		r++;
	}
	if(ans==INT_MAX){
		cout<<"impossible"<<endl;
		return;
	}
	cout<<ans<<endl;

}
int main(){
ios_base::sync_with_stdio(0); 
cin.tie(0); 
cout.tie(0);
//freopen("sum2.in", "r", stdin);
//freopen("sum2.out", "w", stdout);
int tt=1,time=1;
// cin>>tt;
while(tt--){
    solve();
}
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:116:10: warning: unused variable 'time' [-Wunused-variable]
  116 | int tt=1,time=1;
      |          ^~~~

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