Submission #6457499


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
 
#define int long long
#define ll long long
#define vi vector <int>
#define vii vector <pair<int,int> >
#define rep(i,a,b) for (int i=a;i<b;i++)
#define repD(i,a,b) for (int i=a;i>b;i--)
#define pb push_back
#define pii pair <int,int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define MOD 1000000007
#define PI 3.14159265359
 
#define deb(x) {x}
#ifndef local
	#define deb(x) ;
#endif
///----------------------------------------------------------------------------------
 
int n;
int arr[100005];


void solve()
{
	cin>>n;rep(i,0,n)cin>>arr[i];
	
	int ans=0;
	vi source;
	
	source.pb(arr[n-1]);
	
	repD(i,n-2,-1)
	{
		int pos=upper_bound(all(source),arr[i])-source.begin();
		if (pos==source.size())source.pb(arr[i]);
		else source[pos]=arr[i];
	}
	cout<<source.size();
}

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
 
    #ifdef local
    ///freopen("input.txt","r",stdin);
    ///freopen("output.txt","w",stdout);
    clock_t qwertyuiop = clock();
    #endif
 
 
    int t=1;
   // cin>>t;
    
    rep(a,0,t)
    {
        ///cout<<"Case #"<<a+1<<": ";
        solve();
    }
    #ifdef local
	{qwertyuiop = clock() - qwertyuiop;double time_taken = ((double)qwertyuiop)/CLOCKS_PER_SEC;cerr<<fixed<<setprecision(5)<<"\n\nTime Taken : "<<time_taken<<" seconds\n";}
	#endif
}

Submission Info

Submission Time
Task E - Sequence Decomposing
User vyomkesh
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1441 Byte
Status AC
Exec Time 15 ms
Memory 2168 KB

Compile Error

./Main.cpp:21:0: warning: "deb" redefined
  #define deb(x) ;
 ^
./Main.cpp:19:0: note: this is the location of the previous definition
 #define deb(x) {x}
 ^

Judge Result

Set Name All Sample
Score / Max Score 500 / 500 0 / 0
Status
AC × 35
AC × 2
Set Name Test Cases
All all_same, killer_01, killer_02, killer_03, killer_04, killer_05, many_dup_01, many_dup_02, many_dup_03, many_dup_04, many_dup_05, many_dup_06, many_dup_07, many_dup_08, many_dup_09, many_dup_10, many_dup_11, many_dup_12, rand_max_01, rand_max_02, rand_max_03, rand_max_04, rand_max_05, rand_max_06, rand_max_07, rand_max_08, rand_max_09, rand_max_10, rand_max_11, sample_01, sample_02, sorted_ascending, sorted_descending, unique_perm_01, unique_perm_02
Sample sample_01, sample_02
Case Name Status Exec Time Memory
all_same AC 15 ms 2168 KB
killer_01 AC 14 ms 2168 KB
killer_02 AC 13 ms 2168 KB
killer_03 AC 14 ms 2168 KB
killer_04 AC 14 ms 2168 KB
killer_05 AC 14 ms 2168 KB
many_dup_01 AC 15 ms 1024 KB
many_dup_02 AC 15 ms 1024 KB
many_dup_03 AC 15 ms 1024 KB
many_dup_04 AC 15 ms 1152 KB
many_dup_05 AC 15 ms 1152 KB
many_dup_06 AC 14 ms 1024 KB
many_dup_07 AC 15 ms 1408 KB
many_dup_08 AC 15 ms 1408 KB
many_dup_09 AC 13 ms 1408 KB
many_dup_10 AC 14 ms 1660 KB
many_dup_11 AC 15 ms 1660 KB
many_dup_12 AC 15 ms 1408 KB
rand_max_01 AC 15 ms 1024 KB
rand_max_02 AC 14 ms 1024 KB
rand_max_03 AC 14 ms 1024 KB
rand_max_04 AC 14 ms 1024 KB
rand_max_05 AC 14 ms 1024 KB
rand_max_06 AC 15 ms 1024 KB
rand_max_07 AC 14 ms 1024 KB
rand_max_08 AC 15 ms 1024 KB
rand_max_09 AC 14 ms 1024 KB
rand_max_10 AC 15 ms 1024 KB
rand_max_11 AC 14 ms 1024 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sorted_ascending AC 9 ms 1024 KB
sorted_descending AC 12 ms 2168 KB
unique_perm_01 AC 13 ms 1024 KB
unique_perm_02 AC 13 ms 1024 KB