oj.uz

Submission #436399

# Submission time Handle Problem Language Result Execution time Memory
436399 2021-06-24T13:16:21 Z keta_tsimakuridze Exam (eJOI20_exam) C++14
100 / 100
 213 ms 15784 KB 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=5000+5,M=1e5+5,mod=1e9+7;
int t,b[M],a[M],dp[N],ans,n,tree[4*M],r[M],l[M];
map<int,vector<int> > c;
bool ok(int x,int y) {
	if(x<=y && r[x] > y) return 1;
	if(x>y && l[x]<y) return 1;
	return 0;
}
void update(int u,int ind,int l,int r,int val) {
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u] = val;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
	tree[u] = max(tree[2*u],tree[2*u+1]);
}
int getans(int u,int start,int end,int l,int r){
	if(l>end || r<start) return 0;
	if(start<=l && r<=end) return tree[u];
	int mid = (l+r)/2;
	return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
 main(){
 	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	int F = 0;
	for(int i=1;i<=n;i++) {
		cin >> a[i];
	}
	int f = 0;
	for(int i=1;i<=n;i++){
		cin >> b[i];
		if(i-1 && b[i]!=b[i-1]) f = 1;
	} 
	for(int i=1;i<=n;i++) {
		int x = i - 1;
		while(x && a[x] <= a[i]) {
			x = l[x];
		}
		l[i] = x;
	}
	for(int i=n;i>=1;i--){
		int x = i + 1;
		while(x<=n &&  a[x]<=a[i]) {
			x = r[x];
		}
		r[i] = x;
	}
	int ans = 0;
	//f = 1;
	if(!f) {
	
		for(int i=1;i<=n;i++){
			int j = i - 1,F = 0;
			while(j<n && a[j+1] <= b[1]) {
				j ++;
				if(b[1]==a[j]) F = 1;
			}
			if(F) ans += j - i + 1;
			i = max(i,j);
		}
		cout<<ans;
		return 0;
	}	
	for(int i=1;i<=n;i++){
		if(c[a[i]].size()) F = 1;
 		c[a[i]].push_back(i);
		
	}
	if(!F) { 
		for(int i=1;i<=n;i++) {
			if(c[b[i]].size() && ok(c[b[i]][0],i)) {
				int x = getans(1,1,c[b[i]][0],1,n);
				update(1,c[b[i]][0],1,n,x + 1);
			}
		}
		cout<<tree[1];
		
		return 0;
	}

	for(int i=1;i<=n;i++) {
		for(int j=c[b[i]].size() - 1;j>=0;j--) {
			int ind = c[b[i]][j];
			dp[ind] = dp[ind] + ok(ind,i);
		}
		for(int j=1;j<=n;j++) {
			dp[j] = max(dp[j],dp[j-1]);
			ans = max(dp[j],ans);
			
		} //cout<<endl;
	}
	cout<<ans;
}

Compilation message

exam.cpp:30:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 |  main(){
      |  ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 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 8 ms 588 KB Output is correct
3 Correct 21 ms 1608 KB Output is correct
4 Correct 18 ms 1880 KB Output is correct
5 Correct 39 ms 1856 KB Output is correct
6 Correct 18 ms 1856 KB Output is correct
7 Correct 18 ms 1808 KB Output is correct
8 Correct 28 ms 1860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 7 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 992 KB Output is correct
2 Correct 59 ms 5436 KB Output is correct
3 Correct 192 ms 14256 KB Output is correct
4 Correct 195 ms 15064 KB Output is correct
5 Correct 213 ms 15752 KB Output is correct
6 Correct 186 ms 14964 KB Output is correct
7 Correct 161 ms 15784 KB Output is correct
8 Correct 167 ms 14528 KB Output is correct
9 Correct 206 ms 14936 KB Output is correct
10 Correct 142 ms 14916 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 7 ms 972 KB Output is correct
11 Correct 5 ms 972 KB Output is correct
12 Correct 6 ms 1024 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 5 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 177 ms 460 KB Output is correct
25 Correct 113 ms 464 KB Output is correct
26 Correct 108 ms 460 KB Output is correct
27 Correct 114 ms 460 KB Output is correct
28 Correct 103 ms 796 KB Output is correct
29 Correct 103 ms 932 KB Output is correct
30 Correct 108 ms 904 KB Output is correct
31 Correct 104 ms 784 KB Output is correct
32 Correct 102 ms 828 KB Output is correct