Submission #635886

#	Time	Username	Problem	Language	Result	Execution time	Memory
635886		K4YAN	LIS (INOI20_lis)	C++17	20 / 100	47 ms	556 KiB

Main

//Be Name Khoda

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define pllll pair<pll, pll>
#define all(x) x.begin(), x.end()

const ll mxn = 2e3 + 16;
ll n, t, q, w;
vector<ll> g, f, dp;

inline void input() {

    cin >> n;

}

inline void add() {
    f.clear(); dp.clear();
    for(int i = 0; i < q; i++) {
        f.push_back(g[i]);
    } f.push_back(w);
    for(int i = q; i < int(g.size()); i++) {
        f.push_back(g[i]);
    } g = f;
    return;
}
inline void cal_dp() {

    for(int i = 0; i < int(g.size()); i++) {
        q = lower_bound(all(dp), g[i]) - dp.begin();
        if(q == int(dp.size())) {
            dp.push_back(g[i]);
        } else {
            if(dp[q] > g[i]) {
                dp[q] = g[i];
            }
        }
    } return;

}

inline void solve() {

    if(n >= mxn) {
        cout << "Sadge\n";
        return;
    }
    while(n--) {
        cin >> q >> w; q--;
        add();
        cal_dp();
        cout << int(dp.size()) << "\n";
    } return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;
    
}
/*
*/

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80