Submission #947490

#TimeUsernameProblemLanguageResultExecution timeMemory
947490vjudge306 Martian DNA (BOI18_dna)C++14
100 / 100
302 ms14580 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> #define nn "\n" #define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define intt int _; cin >> _; while (_--) #define emp push_back #define mod 1000000007 #define all(v) v.begin(), v.end() #define ld long double #define A first #define B second typedef long long ll; const ld eps = 1e-27; // diff between decimals 0.000000001 mt19937 mt(time(nullptr)); int main() { x_x int n, k, r; cin>>n>>k>>r; map<int,int>mp,f; int ar[n]; for(int i=0; i<n; i++) cin>>ar[i]; int z=0; for(int i=0, a,b; i<r;i++) cin>>a>>b, mp[a]=b, z+=(b==0); int sz=5+n; for(int i=0, j=0; j<n||i<n;) { while (z<r&&j<n) { f[ar[j]]++; if (mp.find(ar[j])!=mp.end()&&f[ar[j]]==mp[ar[j]])z++; j++; } if(z==r&&i<=j)sz=min(sz,j-i); if(mp.find(ar[i])!=mp.end()&&f[ar[i]]==mp[ar[i]]) z-=1; f[ar[i]]-=1; i++; } if(sz>n) cout<<"impossible"; else cout<<sz; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...