Submission #840562

#	Time	Username	Problem	Language	Result	Execution time	Memory
840562		c2zi6	Global Warming (CEOI18_glo)	C++14	17 / 100	344 ms	10956 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 x : tree) cout << x << " "; cout << endl;
            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 tree[N];
            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];
}

vector<int> LIS(vector<int> a, bool rev) {
    vector<int> ans;
    if (rev) reverse(a.begin(), a.end());
    int n = a.size();
    SEG seg(n);
    for (int x : a) {
        if (rev) seg.add(x, seg.opt(x+1, +2e9)+1);
        else seg.add(x, seg.opt(-2e9, x-1)+1);

        ans.push_back(seg.opt(-2e9, +2e9));
    }
    if (rev) reverse(ans.begin(), ans.end());
    return ans;
}

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    compress(a);

    vector<int> lr = LIS(a, false);
    vector<int> rl = LIS(a, true);

    int ans = max(lr[n-1], rl[0]);
    for (int i = 1; i < n; i++) {
        ans = max(ans, lr[i-1] + rl[i]);
    }
    cout << ans << endl;
    return;
    for (int x : lr) cout << x << " "; cout << endl;
    for (int x : rl) cout << x << " "; cout << 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 x : tree) cout << x << " "; cout << endl;
      |             ^~~
glo.cpp:24:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   24 |             for (int x : tree) cout << x << " "; cout << endl;
      |                                                  ^~~~
glo.cpp:25:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   25 |             for (int i = 0; i < n; i++) cout << this->opt(i, i) << " "; cout << endl;
      |             ^~~
glo.cpp:25:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   25 |             for (int i = 0; i < n; i++) cout << this->opt(i, i) << " "; cout << endl;
      |                                                                         ^~~~
glo.cpp: In function 'void solve()':
glo.cpp:83:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   83 |     for (int x : lr) cout << x << " "; cout << endl;
      |     ^~~
glo.cpp:83:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   83 |     for (int x : lr) cout << x << " "; cout << endl;
      |                                        ^~~~
glo.cpp:84:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   84 |     for (int x : rl) cout << x << " "; cout << endl;
      |     ^~~
glo.cpp:84:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   84 |     for (int x : rl) cout << x << " "; cout << endl;
      |                                        ^~~~

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