oj.uz

Submission #731664

# Submission time Handle Problem Language Result Execution time Memory
731664 2023-04-27T18:13:32 Z shadow_sami Martian DNA (BOI18_dna) C++17
40 / 100
 2000 ms 8292 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define fip(a,b) for(ll i = a; i < b ; i++)
#define fjp(a,b) for(ll j = a; j < b ; j++)
#define fp(k,a,b) for(ll k = a; k < b ; k++)
#define fin(a,b) for(ll i = a; i >= b ; i--)
#define fjn(a,b) for(ll i = a; j >= b ; j--)
#define fn(k,a,b) for(ll k = a; k >= b ; k--)
#define fx(a) fx(auto x : a)
#define ordered_set tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>
#define total_one(k) __builtin_popcount(k)
#define back_zero(k) __builtin_ctzll(k)
#define front_zero(k) __builtin_clzll(k)
#define nli "\n"

ll n,m,ans,sum,res,cnt,tptp,tp,tp2,q;

const ll mx = 2e5 + 5;
const ll mod = 1e9 + 7;

ll a[mx];
unordered_map<ll,ll> mp,mp2;
ll st,st2;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	// #ifdef code
		// freopen("input1.txt","r",stdin);
		// freopen("output1.txt","w",stdout);
		// freopen("error1.txt","w",stderr);
	// #endif

		cin>>n>>m>>q;
		fip(1,n+1){
			cin>>a[i];
		}
		fip(0,q){
			cin>>tp>>tp2;
			mp[tp] = tp2;
			st++;
		}
		ans = 1e9;
		fip(1,n+1){
			mp2.clear();
			st2 = 0;
			fjp(i,n+1){
				mp2[a[j]]++;
				if(mp.count(a[j]))
					if(mp[a[j]]==mp2[a[j]])
						st2++;
				if(st2==st)
					ans = min(ans,j-i+1);
			}
		}
		if(ans==1e9){
			cout<<"impossible";
			return 0;
		}
		cout<<ans<<nli;

	// cerr << "Time elapsed : " << setprecision(6) << 100.00 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 348 KB Output is correct
2 Correct 243 ms 364 KB Output is correct
3 Correct 400 ms 492 KB Output is correct
4 Correct 401 ms 528 KB Output is correct
5 Correct 366 ms 436 KB Output is correct
6 Correct 247 ms 352 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 2004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 8292 KB Time limit exceeded
2 Halted 0 ms 0 KB -