Cod sursa(job #2448288)

Utilizator hellhereHell here hellhere Data 16 august 2019 15:08:48
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,a,b) for (int i = a; i <= b; i++)
#define fi(i,a,b) for (int i = a; i < b; i++)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define er erase
#define in insert
#define pi pair <int, int>
#define pii pair <pi, pi>
# define sz(x) (int)((x).size())

int a[100005],ind[100005],pos[100005],n,len;
int bs(int l,int r,int val){
	int ans;
	while(l!=r){
		int mid=(l+r)/2;
		if(a[ind[mid]]<val && a[ind[mid+1]]>val){
			ans=mid+1; l=r;
		}else if(a[ind[mid]]<val)l=mid;else r=mid;
	}
	return ans;
}

int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ifstream cin("scmax.in");
	ofstream cout("scmax.out");
	cin>>n; int top=0,len=0;
	forn(i,1,n){
	cin>>a[i];
	if(a[i]>a[ind[top]]){
		ind[++top]=i;
		len++;
		pos[ind[top]]=ind[top-1];
	}else
	if(a[i]<a[ind[1]]){
		ind[1]=i;
	}else{
		int x=bs(1,top,a[i]);
		ind[x]=i;
		pos[i]=ind[x-1];
	}	
	}
	cout<<len<<'\n';
int pz=ind[top];
vector<int>v;
	while(pz!=0){
		v.pb(a[pz]);
		pz=pos[pz];
	}
	sort(v.begin(),v.end());
	for(auto it:v)cout<<it<<' ';
	return 0;
}
// 11 3 4 -1 5 8 2 3 12 7 9 10