Submission #923721

#	Time	Username	Problem	Language	Result	Execution time	Memory
923721		asdasdqwer	Global Warming (CEOI18_glo)	C++14	0 / 100	91 ms	9160 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

signed main() {
    int n,k;cin>>n>>k;
    vector<int> a(n);
    for (int &x:a)cin>>x;

    vector<int> tmp;
    // different types of operations
    // 1. appended element to array: op.top()[0] == 0
    // 2. changed element at index i: op.top()[0] == 1, op.top()[1] == i, op.top()[2] == oldValue
    stack<array<int,3>> op;
    function<int(int)> bns1=[&](int mx) -> int {
        if (tmp.size() == 0) return -1;
        int l = 0, r = tmp.size() - 1;
        int ans = -1;

        while (l <= r) {
            int m = l + (r-l)/2;
            if (tmp[m] <= mx) {
                ans = m;
                l = m+1;
            }

            else {
                r = m-1;
            }
        }
        return ans;
    };

    for (int i=n-1;i>=0;i--) {
        int idx = bns1(a[i]);
        if (idx == -1) {
            tmp.push_back(a[i]);
            op.push({0, 0, 0});
        }

        else {
            op.push({1, idx, tmp[idx]});
            tmp[idx] = a[i];
        }
    }

    int cand = tmp.size();
    for (int i=0;i<n;i++) {
        a[i] -= k;
    }

    vector<int> lis;

    function<void(array<int,3>)> undo=[&](array<int,3> ope) {
        if (ope[0] == 0) {
            tmp.pop_back();
        }

        else {
            tmp[ope[1]] = ope[2];
        }
    };

    undo(op.top());
    op.pop();

    function<int(int)> bns2=[&](int mx) -> int {
        if (tmp[0] <= mx) return -1;

        int l = 0, r = tmp.size() - 1;
        int ans = -1;

        while (l <= r) {
            int m = l + (r-l)/2;
            if (tmp[m] > mx) {
                ans = m;
                l = m+1;
            }

            else {
                r = m-1;
            }
        }

        return ans;
    };

    for (int i=0;i<n-1;i++) {
        int idx;
        auto it = lower_bound(lis.begin(), lis.end(), a[i]);

        if (it == lis.end()) {
            lis.push_back(a[i]);
            idx = lis.size() - 1;
        }

        else {
            idx = distance(lis.begin(), it);
            lis[idx] = a[i];
        }

        int val = a[i];
        cand = max(cand, idx + 2 + bns2(a[i]));

        undo(op.top());op.pop();
    }

    cout<<cand<<"\n";
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:103:13: warning: unused variable 'val' [-Wunused-variable]
  103 |         int val = a[i];
      |             ^~~

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