Submission #6462937


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mkp make_pair
#define rep(i,s,f) for(i=s;i<f;i++)
#define db cout<<'h'<<'i'<<endl 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PI 3.14159265
#define mod 1000000007
#define mod2 998244353
#define space 100005
#define lg 18
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;

    cin>>n;
    int arr[n];
    rep(i,0,n)cin>>arr[i];

    multimap<int,int> mp;

    mp.insert({arr[n-1],1});

    for(i=n-2;i>=0;i--)
    {
        auto it=mp.upper_bound(arr[i]);
        if(it==mp.end())
        {
            mp.insert({arr[i],1});
        }
        else
        {
            mp.erase(it);
            mp.insert({arr[i],1});
        }
    }
    cout<<mp.size();

    return 0;
}

Submission Info

Submission Time
Task E - Sequence Decomposing
User fros7_
Language C++14 (GCC 5.4.1)
Score 500
Code Size 997 Byte
Status AC
Exec Time 50 ms
Memory 5376 KB

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 50 ms 5376 KB
killer_01 AC 48 ms 5248 KB
killer_02 AC 45 ms 4992 KB
killer_03 AC 48 ms 5248 KB
killer_04 AC 41 ms 3712 KB
killer_05 AC 39 ms 3968 KB
many_dup_01 AC 25 ms 640 KB
many_dup_02 AC 26 ms 640 KB
many_dup_03 AC 25 ms 640 KB
many_dup_04 AC 27 ms 768 KB
many_dup_05 AC 27 ms 896 KB
many_dup_06 AC 25 ms 896 KB
many_dup_07 AC 31 ms 1664 KB
many_dup_08 AC 35 ms 1792 KB
many_dup_09 AC 36 ms 1664 KB
many_dup_10 AC 35 ms 2944 KB
many_dup_11 AC 36 ms 2176 KB
many_dup_12 AC 31 ms 2048 KB
rand_max_01 AC 25 ms 640 KB
rand_max_02 AC 24 ms 640 KB
rand_max_03 AC 24 ms 640 KB
rand_max_04 AC 24 ms 640 KB
rand_max_05 AC 24 ms 640 KB
rand_max_06 AC 24 ms 640 KB
rand_max_07 AC 25 ms 640 KB
rand_max_08 AC 25 ms 640 KB
rand_max_09 AC 24 ms 640 KB
rand_max_10 AC 25 ms 640 KB
rand_max_11 AC 24 ms 640 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sorted_ascending AC 13 ms 640 KB
sorted_descending AC 44 ms 5120 KB
unique_perm_01 AC 22 ms 640 KB
unique_perm_02 AC 23 ms 640 KB