Submission #159943

#	Time	Username	Problem	Language	Result	Execution time	Memory
159943		DS007	Global Warming (CEOI18_glo)	C++14	100 / 100	82 ms	5624 KiB

glo

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, x;
    cin >> n >> x;

    int t[n];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    int lis1[n + 1];
    fill(lis1, lis1 + n + 1, 2e9);
    lis1[0] = -1;

    int len[n], val[n];
    memset(len, 0, sizeof(len));
    int temp = 0, temp1 = -1;

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(lis1, lis1 + n + 1, t[i]);
        *it = t[i];

        /*if (temp > (int)(it - lis1))
            len[i] = temp, val[i] = temp1;
        else if (temp <= (int)(it - lis1))
            len[i] = temp = (int)(it - lis1), val[i] = temp1 = t[i];*/

        len[i] = (int)(it - lis1);
    }

    int lis2[n + 1];
    fill(lis2, lis2 + n + 1, -2e9);
    lis2[n] = 2e9;

    int ans = 1;

    for (int i = n - 1; i >= 0; i--) {
        auto it = upper_bound(lis2, lis2 + n + 1, t[i] - x);
        ans = max(ans, len[i] + n - (int)(it - lis2));
        it = upper_bound(lis2, lis2 + n + 1, t[i]);
        lis2[--it - lis2] = t[i];
    }

    cout << ans;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:20:17: warning: unused variable 'val' [-Wunused-variable]
     int len[n], val[n];
                 ^~~
glo.cpp:22:9: warning: unused variable 'temp' [-Wunused-variable]
     int temp = 0, temp1 = -1;
         ^~~~
glo.cpp:22:19: warning: unused variable 'temp1' [-Wunused-variable]
     int temp = 0, temp1 = -1;
                   ^~~~~

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