Submission #468845

#	Time	Username	Problem	Language	Result	Execution time	Memory
468845		mychecksedad	Exam (eJOI20_exam)	C++17	100 / 100	229 ms	98888 KiB

exam

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, K = 20;
#define pb push_back
#define all(v) v.begin(), v.end()
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 Q(int l, int r){
	int k = __lg((r-l+1));
	return max(rmq[l][k], rmq[r - (1<<k) + 1][k]);
}
int subtask4(){
	map<int, int> m;
	for(int i = 1; i <= n; i++) m[a[i]] = i;
	vector<int> dp(n+2), v, lis(1);
	for(int i = 1; i <= n; i++){
		if(a[i] <= b[i]){
			int pos = m[b[i]];
			if(pos > 0 && Q(min(i, pos), max(i, pos)) <= b[i]){
				v.pb(pos);
			}
		}
	}	
	for(int i = 0; i < v.size(); i++){
		int l = upper_bound(all(lis), v[i]) - lis.begin();
		if(l == lis.size()) lis.pb(v[i]);
		else{
			lis[l] = v[i];
		}
	}
	return int(lis.size())-1;
}
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 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;
}

Compilation message (stderr)

exam.cpp: In function 'int subtask4()':
exam.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
exam.cpp:41:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   if(l == lis.size()) lis.pb(v[i]);
      |      ~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22