oj.uz

Submission #468833

# Submission time Handle Problem Language Result Execution time Memory
468833 2021-08-29T19:30:35 Z mychecksedad Exam (eJOI20_exam) C++17
77 / 100
 230 ms 99020 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, K = 20;
#define pb push_back
int n, a[N], b[N], rmq[N][K];
map<int, vector<int>> m;

int subtask2(){
	int ans = 0;
	vector<bool> is_taken(n + 5, 0);
	for(int i = 1; i <= n; i++){
		if(a[i] == b[1]){
			ans++;
			int l = i-1, r = i + 1;
			is_taken[i] = 1;
			for(; l >= 1 && !is_taken[l] && a[l] < b[1]; l--) ans++, is_taken[l] = 1;
			for(; r <= n && !is_taken[r] && a[r] < b[1]; r++) ans++, is_taken[r] = 1;
		}
	}
	return ans;
}

int subtask4(){
	// map<int, vector<int>> m;
	// for(int i = 1; i <= n; i++) m[a[i]].pb(i);
	// auto last_occ = [](int val, int pos){
	// 	return upper_bound(m[val].begin(), m[val].end(), pos) - m[val].begin();
	// };
	// vector<int> dp(n + 5, 0);
	// for(int i = 1; i <= n; i++){
	// 	dp[i] = dp[i - 1];
	// 	if(a[i] <= b[i]){
	// 		int s = m[b[i]].size();
	// 		if(s == 0) continue;
	// 		int pos = last_occ(b[i], i);			
	// 		if(pos == 0) continue;
	// 		pos--;
	// 		dp[i] = max(dp[i], dp[pos - 1] + num_of_occ(b[i], pos, i));
	// 	}
	// }
	int ans = 0;
	//Will be completed.
	return ans;
}
void precalc(){
	for(int i = 1; i <= n; i++) rmq[i][0] = a[i];
	for(int j = 1; j < K; j++){
		for(int i = 1; i + (1<<j) <= n + 1; i++){
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j - 1]);
		}
	}
}
int Q(int l, int r){
	int k = __lg((r-l+1));
	return max(rmq[l][k], rmq[r - (1<<k) + 1][k]);
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	precalc();
	bool is_b = 1;
	for(int i = 2; i <= n; i++) if(b[i] != b[i - 1]) is_b = 0;
	if(is_b){
		cout << subtask2();
		return 0;
	}
	if(n > 5000){
		cout << subtask4();
		return 0;
	}
	int ans = 0;
	vector<vector<int>> dp(n+2, vector<int>(n+2));
	for(int i = 1; i <= n; i++){
		int mx = 0;
		for(int j = 1; j <= n; j++){
			int x = Q(min(i, j), max(i, j));
			mx = max(mx, dp[i - 1][j]);
			if(x > b[i]){
				dp[i][j] = mx;
			}else{
				if(a[i] <= b[i] && a[j] == b[i]){
					dp[i][j] = mx + 1;
				}else dp[i][j] = mx;
			}
			if(i==n) ans=max(ans, dp[i][j]);
		}
	}


	cout << ans;


	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 6 ms 1996 KB Output is correct
3 Correct 26 ms 8076 KB Output is correct
4 Correct 24 ms 8928 KB Output is correct
5 Correct 38 ms 8900 KB Output is correct
6 Correct 26 ms 8908 KB Output is correct
7 Correct 26 ms 8924 KB Output is correct
8 Correct 37 ms 8876 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 1356 KB Output is correct
3 Correct 33 ms 16268 KB Output is correct
4 Correct 197 ms 91192 KB Output is correct
5 Correct 200 ms 98868 KB Output is correct
6 Correct 205 ms 98884 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 1356 KB Output is correct
9 Correct 33 ms 16268 KB Output is correct
10 Correct 197 ms 91192 KB Output is correct
11 Correct 200 ms 98868 KB Output is correct
12 Correct 205 ms 98884 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 9 ms 4404 KB Output is correct
23 Correct 2 ms 840 KB Output is correct
24 Correct 230 ms 98944 KB Output is correct
25 Correct 203 ms 98948 KB Output is correct
26 Correct 202 ms 98796 KB Output is correct
27 Correct 199 ms 98880 KB Output is correct
28 Correct 218 ms 98856 KB Output is correct
29 Correct 207 ms 98896 KB Output is correct
30 Correct 209 ms 98884 KB Output is correct
31 Correct 211 ms 98884 KB Output is correct
32 Correct 209 ms 99020 KB Output is correct