oj.uz

Submission #468831

# Submission time Handle Problem Language Result Execution time Memory
468831 2021-08-29T19:25:28 Z mychecksedad Exam (eJOI20_exam) C++17
12 / 100
 38 ms 8932 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] = i;
	for(int j = 1; j < K; j++){
		for(int i = 1; i + (1<<j) <= n + 1; i++){
			rmq[i][j] = (a[rmq[i][j - 1]] > a[rmq[i + (1<<(j-1))][j - 1]] ? rmq[i][j - 1] : rmq[i + (1<<(j-1))][j - 1]);
		}
	}
}
int Q(int l, int r){
	int k = __lg((r-l+1));
	return (a[rmq[l][k]] > a[rmq[r - (1<<k) + 1][k]] ? 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(a[x] > b[i]){
				dp[i][j] = mx;
				continue;
			}
			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
0 / 14.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 1996 KB Output is correct
3 Correct 26 ms 8000 KB Output is correct
4 Correct 25 ms 8852 KB Output is correct
5 Correct 38 ms 8920 KB Output is correct
6 Correct 26 ms 8832 KB Output is correct
7 Correct 27 ms 8908 KB Output is correct
8 Correct 36 ms 8932 KB Output is correct

Subtask #3
0 / 13.0

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

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
0 / 16.0

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

Subtask #6
0 / 22.0

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