Submission #501006

#	Time	Username	Problem	Language	Result	Execution time	Memory
501006		blue	Global Warming (CEOI18_glo)	C++17	100 / 100	179 ms	6372 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*

Obs 1. If the temperature is increased, then it is optimal to increase the temperature of an interval containing
       a suffix of the LIS.

Obs 2. The temperatures should be increased for a suffix of the given array, by +x.

*/
int n, x;
int t[200001];

int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> t[i];

    int I[2*n];
    for(int i = 0; i < n; i++)
    {
        I[i] = i+1;
        I[i+n] = -i-1;
    }

    sort(I, I + 2*n, [] (int p, int q)
    {
        int a1 = (p > 0 ? t[p] : t[-p] + x);
        int a2 = (q > 0 ? t[q] : t[-q] + x);

        if(a1 == a2) return abs(p) > abs(q);    // if specific test cases fail, check this part.
        return a1 < a2;
    });

    vector<int> lis0(n+1, 0), lis1(n+1, 0); //before increase, after increase

    int res = 0;

    for(int i:I)
    {

        // cout << i << ' ';
        if(i > 0)
        {
            for(int j = i-1; j >= 1; j -= j&-j) lis0[i] = max(lis0[i], lis0[j]);
            lis0[i]++;

            res = max(res, lis0[i]);

            for(int j = i; j <= n; j += j&-j) lis0[j] = max(lis0[j], lis0[i]);

        }
        else
        {
            for(int j = -i-1; j >= 1; j -= j&-j) lis1[-i] = max(lis1[-i], max(lis0[j], lis1[j]));
            lis1[-i]++;

            res = max(res, lis1[-i]);

            for(int j = -i; j <= n; j += j&-j) lis1[j] = max(lis1[j], lis1[-i]);
        }
    }
    // cout << '\n';

    cout << res << '\n';
}

• 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