Submission #824192

#	Time	Username	Problem	Language	Result	Execution time	Memory
824192		vanic	Exam (eJOI20_exam)	C++14	100 / 100	490 ms	99520 KiB

exam

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cstring>

using namespace std;

const int maxn=1e5+5;

int n;
int a[maxn], b[maxn];

void solve1(){
	int val=b[0];
	bool p=0;
	int prosl=-1;
	int br=0;
	for(int i=0; i<n; i++){
		if(a[i]==val && !p){
			br+=i-prosl;
			p=1;
		}
		else if(a[i]>val){
			prosl=i;
			p=0;
		}
		else if(p){
			br++;
		}
	}
	cout << br << '\n';
}

int l[maxn], r[maxn];
map < int, int > pos;
vector < int > lis;

void dodaj(int x){
	int ind=upper_bound(lis.begin(), lis.end(), x)-lis.begin();
	if(ind==(int)lis.size()){
		lis.push_back(x);
	}
	else{
		lis[ind]=x;
	}
}

void solve2(){
	stack < pair < int, int > > s;
	s.push({2e9, -1});
	for(int i=0; i<n; i++){
		pos[a[i]]=i;
		while(s.top().first<a[i]){
			s.pop();
		}
		l[i]=s.top().second+1;
		s.push({a[i], i});
	}
	while(!s.empty()){
		s.pop();
	}
	s.push({2e9, n});
	for(int i=n-1; i>-1; i--){
		while(s.top().first<a[i]){
			s.pop();
		}
		r[i]=s.top().second-1;
		s.push({a[i], i});
	}
	for(int i=0; i<n; i++){
		if(pos.find(b[i])!=pos.end() && i>=l[pos[b[i]]] && i<=r[pos[b[i]]]){
			dodaj(pos[b[i]]);
		}
	}
	cout << lis.size() << '\n';
}


int dp[5005][5005];

int rek(int x, int y){
	if(x==-1 || y==-1){
		return 0;
	}
	if(dp[x][y]!=-1){
		return dp[x][y];
	}
	if(a[x]==b[y] && l[x]<=y && r[x]>=y){
		return dp[x][y]=max(rek(x-1, y), rek(x, y-1)+1);
	}
	else{
		return dp[x][y]=max(rek(x-1, y), rek(x, y-1));
	}
}

void solve3(){
	memset(dp, -1, sizeof(dp));
	stack < pair < int, int > > s;
	s.push({2e9, -1});
	for(int i=0; i<n; i++){
		while(s.top().first<a[i]){
			s.pop();
		}
		l[i]=s.top().second+1;
		s.push({a[i], i});
	}
	while(!s.empty()){
		s.pop();
	}
	s.push({2e9, n});
	for(int i=n-1; i>-1; i--){
		while(s.top().first<a[i]){
			s.pop();
		}
		r[i]=s.top().second-1;
		s.push({a[i], i});
	}
	cout << rek(n-1, n-1) << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	set < int > s;
	for(int i=0; i<n; i++){
		cin >> a[i];
		s.insert(a[i]);
	}
	bool p=1;
	for(int i=0; i<n; i++){
		cin >> b[i];
		if(i && b[i]!=b[i-1]){
			p=0;
		}
	}
	if(p){
		solve1();
	}
	else if((int)s.size()==n){
		solve2();
	}
	else{
		solve3();
	}
	return 0;
}

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