Submission #714834

#	Time	Username	Problem	Language	Result	Execution time	Memory
714834		thimote75	Global Warming (CEOI18_glo)	C++14	100 / 100	418 ms	14672 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#define num long long

// LIS maintainer
struct LISm {
    map<num, num> d;

    void insert (num id, num res) {
        if (query(id) >= res) return ;
        if (d.find(id) != d.end())
            d.erase(id);

        d.insert({ id, res });

        auto it = d.find(id);
        while (true) {
            it ++;
            if (it == d.end()) break ;
            if ((*it).second > res) break ;

            d.erase((*it).first);
            it = d.find(id);
        }
    }

    // returns the second value of the last iterator such that key < x
    num query (num x) {
        if (d.empty()) return 0;

        auto it = d.lower_bound(x); // first iterator such that key >= x
        if (it == d.begin()) return 0;
        it --; // last iterator such that key < x

        return (*it).second;
    }
    void show () {
        for (auto u : d)
            printf("%lld->%lld ", u.first, u.second);
        printf("\n");
    }
};

int main () {
    LISm lis_0;
    LISm lis_x;

    int nbTemp; num maxDelta;
    cin >> nbTemp >> maxDelta;

    num result = 0;

    for (int idTemp = 0; idTemp < nbTemp; idTemp ++) {
        num temp;
        cin >> temp;
        num temp_x = temp + maxDelta;

        num lis_0_value = 1 + lis_0.query(temp);
        num lis_x_value = 1 + max( lis_0.query(temp_x), lis_x.query(temp_x) );

        //printf("\n--- %d %lld ---\n", idTemp, temp);
        //printf("%d: 0(%lld) +x(%lld)\n", idTemp, lis_0_value, lis_x_value);

        lis_0.insert( temp,   lis_0_value );
        //lis_0.show();
        lis_x.insert( temp_x, lis_x_value );
        //lis_x.show();
    
        result = max(result, lis_0_value);
        result = max(result, lis_x_value);
    }

    cout << result;
}

• 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