Submission #759925

#	Time	Username	Problem	Language	Result	Execution time	Memory
759925		The_Samurai	LIS (INOI20_lis)	C++17	0 / 100	161 ms	340 KiB

Main

#include "bits/stdc++.h"

using namespace std;

struct SegTree {
    int len, neutral_element = 0;
    vector<int> tree;

    void init(int n) {
        len = 1;
        while (len < n) len *= 2;
        tree.assign(2 * len, 0);
    }

    SegTree(int n) {
        init(n);
    }

    SegTree() {}

    inline int type(int a, int b) {
        return max(a, b);
    }

    void set(int i, int v) {
        i += len;
        tree[i] = type(tree[i], v);
        while (i > 1) {
            i >>= 1;
            tree[i] = type(tree[i << 1], tree[i << 1 | 1]);
        }
    }

    int get(int l, int r, int lx, int rx, int x) {
        if (l >= rx or lx >= r) {
            return neutral_element;
        }
        if (l <= lx and rx <= r) {
            return tree[x];
        }
        int m = (lx + rx) >> 1;
        return type(get(l, r, lx, m, x << 1), get(l, r, m, rx, x << 1 | 1));
    }

    int get(int l, int r) {
        // [l, r]
        if (r < 0) {
            return neutral_element;
        }
        return get(l, r + 1, 0, len, 1);
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    vector<int> a, ans;
    SegTree sg;
    auto calc = [&]() {
        int n = a.size();
        ans.resize(n, 0);
        map<int, int> mp;
        sg.init(n);
        for (int x: a) {
            mp[x];
        }
        int z = 0;
        for (auto &it: mp) {
            it.second = z++;
        }
        for (int i = 0; i < n; i++) {
            int x = mp[a[i]];
//            cout << x << ' ';
            ans[i] = sg.get(0, x - 1) + 1;
            sg.set(i, ans[i]);
        }
//        cout << endl;
    };
    int q;
    cin >> q;
    while (q--) {
        int i, x;
        cin >> i >> x;
        i--;
        a.insert(a.begin() + i, x);
        calc();
        cout << sg.tree[1] << '\n';
    }
}

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