[C/C++] Codeforce 486E - LIS of Sequence

E. LIS of Sequence

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.

Nam created a sequence a consisting of n (1 ≤ n ≤ 105) elements a1, a2, ..., an (1 ≤ ai ≤ 105). A subsequence ai1, ai2, ..., aik where 1 ≤ i1 < i2 < ... < ik ≤ n is called increasing if ai1 < ai2 < ai3 < ... < aik. An increasing subsequence is called longest if it has maximum length among all increasing subsequences.

Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes i (1 ≤ i ≤ n), into three groups:

1. group of all i such that ai belongs to no longest increasing subsequences.
2. group of all i such that ai belongs to at least one but not every longest increasing subsequence.
3. group of all i such that ai belongs to every longest increasing subsequence.

Since the number of longest increasing subsequences of a may be very large, categorizing process is very difficult. Your task is to help him finish this job.

Input

The first line contains the single integer n (1 ≤ n ≤ 105) denoting the number of elements of sequence a.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 105).

Output

Print a string consisting of n characters. i-th character should be '1', '2' or '3' depending on which group among listed above index i belongs to.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> Last;
int N;
int AA[100005];
int LL[100005];
int BB[100005];
int SS[100005];
int TT[100005];
int ans[100005];

void LIS(int A[], int L[])
{
	vector<int>::iterator it;
	Last.push_back(-100);
	for (int i = 1; i <=N; i++)
	{
		if (Last.back() < A[i])
		{
			Last.push_back(A[i]);
		}

		it = lower_bound(Last.begin(), Last.end(), A[i]);
		*it = A[i];
		L[i] = it - Last.begin();
	}
}

int main()
{
	int LEN, maxi, mini;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &AA[i]);
	}

	LIS(AA, LL);
	LEN = 0;
	for (int i = 1; i <= N; i++)
	{
		LEN = max(LEN, LL[i]);
	}
	Last.clear();
	for (int i = 1; i <= N; i++)
	{
		BB[N - i + 1] = 1000000 - AA[i];
	}
	LIS(BB, SS);
	for (int i = 1; i <= N; i++)
	{
		TT[N - i + 1] = SS[i];
	}

	for (int i = 1; i <= N; i++)
	{
		ans[i] = 1;
	}

	for (int i = 1; i <= N; i++)
	{
		if (LL[i] + TT[i] == LEN + 1) ans[i] = 3;
	}
	maxi = 0;
	for (int i = 1; i <= N; i++)
	{
		if (ans[i] != 1)
		{
			if (AA[i] <= maxi) ans[i] = 2;
			maxi = max(maxi, AA[i]);
		}
	}
	mini = 1000000;
	for (int i = N; i >= 1; i--)
	{
		if (ans[i] != 1)
		{
			if (AA[i] >= mini) ans[i] = 2;
			mini = min(mini, AA[i]);
		}
	}
	
	for(int i = 1; i <= N; i++)
	{
		printf("%d", ans[i]);
	}
	printf("\n");


	return 0;

}

 

 

https://codeforces.com/problemset/problem/486/E

Problem - 486E - Codeforces