Submission #468845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
468845	2021-08-29T19:59:07 Z	mychecksedad	Exam (eJOI20_exam)	C++17	100 / 100	229 ms	98888 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 = 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

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	204 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	1996 KB	Output is correct
3	Correct	25 ms	8032 KB	Output is correct
4	Correct	27 ms	8920 KB	Output is correct
5	Correct	39 ms	8840 KB	Output is correct
6	Correct	27 ms	8912 KB	Output is correct
7	Correct	29 ms	8908 KB	Output is correct
8	Correct	34 ms	8844 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	3 ms	1356 KB	Output is correct
3	Correct	35 ms	16252 KB	Output is correct
4	Correct	193 ms	91024 KB	Output is correct
5	Correct	202 ms	98848 KB	Output is correct
6	Correct	202 ms	98844 KB	Output is correct

Subtask #4
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	972 KB	Output is correct
2	Correct	28 ms	5760 KB	Output is correct
3	Correct	79 ms	13924 KB	Output is correct
4	Correct	100 ms	14020 KB	Output is correct
5	Correct	87 ms	14608 KB	Output is correct
6	Correct	85 ms	15704 KB	Output is correct
7	Correct	109 ms	16324 KB	Output is correct
8	Correct	90 ms	15156 KB	Output is correct
9	Correct	103 ms	15692 KB	Output is correct
10	Correct	66 ms	15808 KB	Output is correct

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	204 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	204 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	1 ms	204 KB	Output is correct
8	Correct	3 ms	1356 KB	Output is correct
9	Correct	35 ms	16252 KB	Output is correct
10	Correct	193 ms	91024 KB	Output is correct
11	Correct	202 ms	98848 KB	Output is correct
12	Correct	202 ms	98844 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	9 ms	4300 KB	Output is correct
23	Correct	2 ms	716 KB	Output is correct
24	Correct	229 ms	98844 KB	Output is correct
25	Correct	222 ms	98884 KB	Output is correct
26	Correct	200 ms	98816 KB	Output is correct
27	Correct	200 ms	98888 KB	Output is correct
28	Correct	200 ms	98756 KB	Output is correct
29	Correct	207 ms	98756 KB	Output is correct
30	Correct	208 ms	98852 KB	Output is correct
31	Correct	207 ms	98852 KB	Output is correct
32	Correct	208 ms	98852 KB	Output is correct

Submission #468845

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 12.0 / 12.0

Subtask #3 13.0 / 13.0

Subtask #4 23.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
23.0 / 23.0

Subtask #5
16.0 / 16.0

Subtask #6
22.0 / 22.0