Submission #468843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
468843	2021-08-29T19:56:02 Z	mychecksedad	Exam (eJOI20_exam)	C++17	77 / 100	249 ms	98932 KB

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 = lower_bound(all(lis), v[i]) - lis.begin();
		if(l == lis.size()) lis.pb(v[i]);
		else if(lis[l]){
			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

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.0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	332 KB	Output is correct
4	Correct	204 KB	Output is correct
5	Correct	204 KB	Output is correct
6	Correct	204 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	2004 KB	Output is correct
3	Correct	28 ms	8024 KB	Output is correct
4	Correct	30 ms	8876 KB	Output is correct
5	Correct	49 ms	8900 KB	Output is correct
6	Correct	28 ms	8916 KB	Output is correct
7	Correct	26 ms	8896 KB	Output is correct
8	Correct	39 ms	8888 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	3 ms	1356 KB	Output is correct
3	Correct	33 ms	16164 KB	Output is correct
4	Correct	227 ms	91152 KB	Output is correct
5	Correct	204 ms	98852 KB	Output is correct
6	Correct	204 ms	98852 KB	Output is correct

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	972 KB	Output is correct
2	Correct	30 ms	6520 KB	Output is correct
3	Correct	84 ms	15084 KB	Output is correct
4	Correct	84 ms	15912 KB	Output is correct
5	Incorrect	92 ms	16588 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 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	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	3 ms	1356 KB	Output is correct
9	Correct	33 ms	16164 KB	Output is correct
10	Correct	227 ms	91152 KB	Output is correct
11	Correct	204 ms	98852 KB	Output is correct
12	Correct	204 ms	98852 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 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	8 ms	4300 KB	Output is correct
23	Correct	2 ms	716 KB	Output is correct
24	Correct	249 ms	98852 KB	Output is correct
25	Correct	207 ms	98848 KB	Output is correct
26	Correct	206 ms	98852 KB	Output is correct
27	Correct	198 ms	98756 KB	Output is correct
28	Correct	215 ms	98784 KB	Output is correct
29	Correct	206 ms	98756 KB	Output is correct
30	Correct	213 ms	98932 KB	Output is correct
31	Correct	207 ms	98824 KB	Output is correct
32	Correct	211 ms	98852 KB	Output is correct

Submission #468843

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 12.0 / 12.0

Subtask #3 13.0 / 13.0

Subtask #4 0 / 23.0

Subtask #5 16.0 / 16.0

Subtask #6 22.0 / 22.0

Subtask #1
14.0 / 14.0

Subtask #2
12.0 / 12.0

Subtask #3
13.0 / 13.0

Subtask #4
0 / 23.0

Subtask #5
16.0 / 16.0

Subtask #6
22.0 / 22.0