Submission #840514

#	Time	Username	Problem	Language	Result	Execution time	Memory
840514		c2zi6	Global Warming (CEOI18_glo)	C++14	10 / 100	72 ms	3224 KiB

glo

#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
using ll = long long;

class SEG {
    public:
        SEG(int m) {
            n = 1;
            while (n < m) n <<= 1;
            tree = vector<int>(2 * n);
        }
        void add(int h, int s) {
            this->update(0, 0, n-1, h, s);
        }
        int opt(int l, int r) {
            l = max(l, 0);
            r = min(r, n-1);
            return this->get(0, 0, n-1, l, r);
        }
        void print() {
            for (int i = 0; i < n; i++) cout << this->opt(i, i) << " "; cout << endl;
        }
    private:
        int n;
        vector<int> tree;
        int get(int N, int L, int R, int l, int r) {
            if (l <= L && R <= r) return tree[N];
            if (R < l || L > r) return 0;
            int M = (L + R) / 2;
            return max(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
        }
        int update(int N, int L, int R, int i, int x) {
            if (i < L || i > R) return 0;
            if (L == R) return tree[N] = max(tree[N], x);;
            int M = (L + R) / 2;
            return tree[N] = max(update(2*N+1, L, M, i, x), update(2*N+2, M+1, R, i, x));
        }
};

void compress(vector<int>& a) {
    map<int, int> mp;
    for (int x : a) mp[x] = 0;
    int i = 0;
    for (pair<int, int> p : mp) mp[p.ff] = i++;
    for (int& x : a) x = mp[x];
}

int LIS(vector<int> a) {
    int n = a.size();
    vector<int> dp(n+1, 2e9);
    dp[0] = -2e9;
    for (int x : a) {
        *(lower_bound(dp.begin(), dp.end(), x)) = x;
    }
    int ans = 0;
    while (ans+1 <= n && dp[ans+1] != 2e9) ans++;
    return ans;
}

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    cout << LIS(a) << endl; return;
    compress(a);
    //for (int x : a) cout << x << " "; cout << endl;

    SEG seg(n);
    for (int x : a) {
        seg.add(x, seg.opt(-2e9, x-1)+1);
    }
    
    cout << seg.opt(-2e9, +2e9) << endl;
}

int main() {
	int t = 1;
    //cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

glo.cpp: In member function 'void SEG::print()':
glo.cpp:24:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   24 |             for (int i = 0; i < n; i++) cout << this->opt(i, i) << " "; cout << endl;
      |             ^~~
glo.cpp:24:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   24 |             for (int i = 0; i < n; i++) cout << this->opt(i, i) << " "; cout << endl;
      |                                                                         ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25