Submission #6467438


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> q;
    int a;
    REP(i, n) {
        cin >> a;
        if (q.empty()) {
            q.push_back(a);
        } else {
            auto x = lower_bound(ALL(q), a);
            if (x == q.begin()) {
                auto x = upper_bound(ALL(q), a);
                q.insert(x, a);
            } else {
                q.erase(x - 1);
                auto x = upper_bound(ALL(q), a);
                q.insert(x, a);
            }
        }
    }
    cout << q.size() << endl;
}

Submission Info

Submission Time
Task E - Sequence Decomposing
User mdstoy
Language C++14 (GCC 5.4.1)
Score 500
Code Size 974 Byte
Status
Exec Time 731 ms
Memory 892 KB

Test Cases

Set Name Score / Max Score Test Cases
All 500 / 500 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 0 / 0 sample_01, sample_02
Case Name Status Exec Time Memory
all_same 48 ms 892 KB
killer_01 731 ms 892 KB
killer_02 652 ms 892 KB
killer_03 729 ms 892 KB
killer_04 385 ms 892 KB
killer_05 427 ms 892 KB
many_dup_01 58 ms 256 KB
many_dup_02 61 ms 256 KB
many_dup_03 74 ms 256 KB
many_dup_04 84 ms 256 KB
many_dup_05 96 ms 256 KB
many_dup_06 82 ms 256 KB
many_dup_07 236 ms 512 KB
many_dup_08 273 ms 512 KB
many_dup_09 229 ms 512 KB
many_dup_10 363 ms 640 KB
many_dup_11 325 ms 640 KB
many_dup_12 272 ms 512 KB
rand_max_01 55 ms 256 KB
rand_max_02 54 ms 256 KB
rand_max_03 52 ms 256 KB
rand_max_04 54 ms 256 KB
rand_max_05 52 ms 256 KB
rand_max_06 53 ms 256 KB
rand_max_07 54 ms 256 KB
rand_max_08 55 ms 256 KB
rand_max_09 52 ms 256 KB
rand_max_10 56 ms 256 KB
rand_max_11 70 ms 256 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sorted_ascending 28 ms 256 KB
sorted_descending 684 ms 892 KB
unique_perm_01 43 ms 256 KB
unique_perm_02 44 ms 256 KB