Submission #858365

#	Time	Username	Problem	Language	Result	Execution time	Memory
858365		ily2003	Baloni (COCI15_baloni)	C++14	0 / 100	2084 ms	9620 KiB

baloni

#include <bits/stdc++.h>
using namespace std;
int n,a[1000001];
vector <int> vec;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i=1;i<=n;++i) cin >> a[i];
    for (int i=1;i<=n;++i) {
        if (vec.empty() || a[i]+1>vec.back()) vec.push_back(a[i]);
        else {
            int so=lower_bound(vec.begin(),vec.end(),a[i]+1)-vec.begin();
            if (vec[so]==a[i]+1) vec[so]=a[i];
            else vec.insert(vec.begin()+max(so-1,0),a[i]);
        }
    }
    cout << vec.size();
    return 0;
}

• Subtask 1: 0 / 100