oj.uz

Submission #927132

# Submission time Handle Problem Language Result Execution time Memory
927132 2024-02-14T09:56:55 Z vjudge1 Martian DNA (BOI18_dna) C++17
68 / 100
 2000 ms 612024 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
typedef long long ll;

const ll mod=1e9+7;
const ll inf=1e9+7;
const int N=5e5+4;

int n,k,r;
int a[N];
map<int,int>mp,cur;
set<int>st[N];
multiset<int>mst;

void solve(){
	cin>>n>>k>>r;
	for(int i=1; i<=n; ++i){
		cin>>a[i];
	}
	ll all=0;
	for(int i=1; i<=r; ++i){
		int tp,cn;
		cin>>tp>>cn;
		mp[tp]=cn;
		for(int x=0; x<cn; ++x) {
			mst.insert(tp);
			++all;
//			if(all>n){
		//		cout<<"impossible\n";
	//			return;
			//}
		}
	}
	int l=0,r=0;
	int ans=inf;
	while(1){
		if(l==r && r==n) break;
		//cout<<l<<' '<<r<<endl;
		//cout<<mst.size()<<endl;
		while(r+1<=n && mst.size()){
			++r;
			auto pos=mst.find(a[r]);
			cur[a[r]]++;
			//cout<<a[r]<<"  "<<cur[a[r]]<<endl;
			if(pos!=mst.end()) mst.erase(pos);
		}
		if(r==n && mst.size()) {
			break;
		}
		ans=min(ans,r-l);
		while(l+1<=r){
			while(l+1<=r && mp[a[l+1]]==0) ++l;
			ans=min(ans,r-l);
			if(l+1>r) break; 
			++l;
			cur[a[l]]--;
			//cout<<a[l]<<' '<<cur[a[l]]<<endl;
		//	return;
			if(cur[a[l]]<mp[a[l]]) {
				mst.insert(a[l]);
				break;
			}
			ans=min(ans,r-l);
		}
	}
	if(ans==inf){
		cout<<"impossible\n";
		return;
	}
	cout<<ans<<endl;
}
			
int main(){
	int tt=1;
	//cin>>tt;
	while(tt--) {
		solve();
	}
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25176 KB Output is correct
2 Correct 5 ms 25180 KB Output is correct
3 Correct 5 ms 25428 KB Output is correct
4 Correct 5 ms 25180 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 5 ms 25180 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 7 ms 25180 KB Output is correct
4 Correct 7 ms 25400 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25220 KB Output is correct
7 Correct 7 ms 25212 KB Output is correct
8 Correct 6 ms 25220 KB Output is correct
9 Correct 5 ms 25180 KB Output is correct
10 Correct 5 ms 25180 KB Output is correct
11 Correct 5 ms 25180 KB Output is correct
12 Correct 5 ms 25236 KB Output is correct
13 Correct 5 ms 25216 KB Output is correct
14 Correct 6 ms 25180 KB Output is correct
15 Correct 6 ms 25176 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29264 KB Output is correct
2 Correct 42 ms 26964 KB Output is correct
3 Correct 39 ms 25180 KB Output is correct
4 Correct 45 ms 27984 KB Output is correct
5 Correct 124 ms 32648 KB Output is correct
6 Correct 77 ms 34608 KB Output is correct
7 Correct 48 ms 25224 KB Output is correct
8 Correct 184 ms 39580 KB Output is correct
9 Correct 73 ms 25940 KB Output is correct
10 Correct 65 ms 28500 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 7 ms 25180 KB Output is correct
14 Correct 7 ms 25488 KB Output is correct
15 Correct 7 ms 25212 KB Output is correct
16 Correct 6 ms 25260 KB Output is correct
17 Correct 6 ms 25180 KB Output is correct
18 Correct 6 ms 25180 KB Output is correct
19 Correct 6 ms 25176 KB Output is correct
20 Correct 6 ms 25180 KB Output is correct
21 Correct 5 ms 25220 KB Output is correct
22 Correct 7 ms 25180 KB Output is correct
23 Correct 5 ms 25176 KB Output is correct
24 Correct 5 ms 25180 KB Output is correct
25 Correct 5 ms 25180 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 32908 KB Output is correct
2 Correct 203 ms 30736 KB Output is correct
3 Correct 146 ms 30844 KB Output is correct
4 Correct 39 ms 25180 KB Output is correct
5 Execution timed out 2084 ms 612024 KB Time limit exceeded
6 Halted 0 ms 0 KB -