oj.uz

Submission #831147

# Submission time Handle Problem Language Result Execution time Memory
831147 2023-08-19T19:39:24 Z pera Exam (eJOI20_exam) C++17
62 / 100
 97 ms 28092 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int N = 2e5 + 1;

vector<int> t(4 * N) , x(4 * N) , a(N) , b(N) , L(N) , R(N);
map<int , int> M;

void up(int v , int l ,int r , int p , int x){
	if(l == r){
		t[v] = x;
		return;
	}
	int m = (l + r) / 2;
	if(p <= m) up(v * 2 , l , m , p , x);
	else up(v * 2 + 1 , m + 1 , r , p , x);
	t[v] = max(t[v * 2] , t[v * 2 + 1]);
}

int g(int v , int l , int r , int L , int R){
	if(l > r || r < L || l > R) return 0;
	if(L <= l && r <= R) return t[v];
	int m = (l + r) / 2;
	return max(g(v * 2 , l , m , L , R) , g(v * 2 + 1 , m + 1 , r , L , R));
}
 
main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n , oK = 1;cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		M[a[i]] = i;
	}
	for(int i = 1;i <= n;i ++){
		cin >> b[i];
		if(i != 1) oK &= (b[i] == b[i - 1]);
	}
	for(int i = 1;i <= n;i ++){
		L[i] = i - 1;
		while(L[i] && a[L[i]] <= a[i]) L[i] = L[L[i]];
	}
	for(int i = n;i >= 1;i --){
		R[i] = i + 1;
		while(R[i] != n + 1 && a[R[i]] <= a[i]) R[i] = R[R[i]];
	}
	if(oK){
		int c = 0;
		for(int i = 1;i <= n;i ++){
			int cc = 0 , k = 0;
			while(a[i] <= b[i] && i <= n){
				if(a[i] == b[i]) k = 1;
				++ cc , ++ i; 
			}
			if(k) c += cc;
		}
		cout << c << endl;
		return 0;
	}
	oK = 1;
	for(int i = 2;i <= n;i ++){
		oK &= (a[i] > a[i - 1]);
	}
	if(oK){
		vector<int> dp(n + 1);
		dp[1] = (a[1] == b[1]);
		for(int i = 2;i <= n;i ++){
			int q = 0;
			for(int j = i;j >= 1;j --){
				q += (a[i] == b[j]);
				dp[i] = max(dp[i] , q + dp[j - 1]);
			}
			for(int j = 1;j <= i;j ++){
				dp[j] = max(dp[j] , dp[j - 1] + (a[i] == b[j]));
			}
		}
		cout << *max_element(dp.begin() , dp.end()) << endl;
		return 0;
	}
	if(M.size() == n){
		vector<int> ans(n + 1);
		for(int i = 1;i <= n;i ++){
			if(M.find(b[i]) != M.end()){
				int p = M[b[i]];
				if(L[p] < i && i < R[p]){
					ans[i] = g(1 , 1 , n , 1 , p) + 1;
					up(1 , 1 , n , p , ans[i]);
				}
			}
		}
		cout << *max_element(ans.begin() , ans.end()) << endl;
		return 0;
	}
	assert(n <= 5000);
	vector<vector<int>> dp(n + 1 , vector<int>(n + 1));
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= n;j ++){
			if(a[i] == b[j] && L[i] < j && j < R[j]){
				dp[i][j] = dp[i][j - 1] + 1;
			}
			dp[i][j] = max({dp[i][j] , dp[i - 1][j] , dp[i][j - 1]});
		}
	}
	cout << dp[n][n] << endl;
}

Compilation message

exam.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~
exam.cpp: In function 'int main()':
exam.cpp:82:14: warning: comparison of integer expressions of different signedness: 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   82 |  if(M.size() == n){
      |     ~~~~~~~~~^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 7 ms 19128 KB Output is correct
3 Correct 7 ms 19028 KB Output is correct
4 Correct 7 ms 19028 KB Output is correct
5 Correct 7 ms 19028 KB Output is correct
6 Correct 8 ms 19028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19140 KB Output is correct
2 Correct 12 ms 19424 KB Output is correct
3 Correct 32 ms 25040 KB Output is correct
4 Correct 16 ms 19396 KB Output is correct
5 Correct 69 ms 25832 KB Output is correct
6 Correct 18 ms 19412 KB Output is correct
7 Correct 20 ms 19524 KB Output is correct
8 Correct 54 ms 23500 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19028 KB Output is correct
2 Correct 8 ms 19156 KB Output is correct
3 Correct 19 ms 19304 KB Output is correct
4 Correct 61 ms 19500 KB Output is correct
5 Correct 67 ms 19512 KB Output is correct
6 Correct 65 ms 19564 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19540 KB Output is correct
2 Correct 33 ms 22644 KB Output is correct
3 Correct 82 ms 27188 KB Output is correct
4 Correct 82 ms 28008 KB Output is correct
5 Correct 96 ms 28092 KB Output is correct
6 Correct 97 ms 27320 KB Output is correct
7 Correct 86 ms 28000 KB Output is correct
8 Correct 84 ms 27212 KB Output is correct
9 Correct 90 ms 27316 KB Output is correct
10 Correct 68 ms 27196 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 7 ms 19128 KB Output is correct
3 Correct 7 ms 19028 KB Output is correct
4 Correct 7 ms 19028 KB Output is correct
5 Correct 7 ms 19028 KB Output is correct
6 Correct 8 ms 19028 KB Output is correct
7 Incorrect 9 ms 19116 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 7 ms 19128 KB Output is correct
3 Correct 7 ms 19028 KB Output is correct
4 Correct 7 ms 19028 KB Output is correct
5 Correct 7 ms 19028 KB Output is correct
6 Correct 8 ms 19028 KB Output is correct
7 Correct 7 ms 19028 KB Output is correct
8 Correct 8 ms 19156 KB Output is correct
9 Correct 19 ms 19304 KB Output is correct
10 Correct 61 ms 19500 KB Output is correct
11 Correct 67 ms 19512 KB Output is correct
12 Correct 65 ms 19564 KB Output is correct
13 Incorrect 9 ms 19116 KB Output isn't correct
14 Halted 0 ms 0 KB -