Submission #482620

#	Time	Username	Problem	Language	Result	Execution time	Memory
482620		Ozy	Global Warming (CEOI18_glo)	C++17	38 / 100	113 ms	9636 KiB

glo

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 200000
#define LIM 2000000001
#define alt first
#define val second

lli n,x,res,a,num;
lli arr[MAX+2] , elevados[MAX+2];
set<pair<lli,lli> > lis;
set<pair<lli,lli> >::iterator it,pas;
bool gf;

void LIS(lli act,lli pos) {

    pair<lli,lli> nuevo;

    if (lis.empty()) lis.insert({act,1ll});
    else {

        it = lis.lower_bound({act,0});
        if (it == lis.begin()) nuevo = {act,1};
        else {
            it--;
            nuevo = {act, (*it).val + 1};
        }

        it++;
        while (true) {

            if (it == lis.end()) break;
            if ( (*it).val > nuevo.val) break;

            pas = it;
            it++;
            lis.erase(pas);

        }
        lis.insert({nuevo});
    }

}


void LISa(lli act,lli pos) {

    pair<lli,lli> nuevo;

    if (lis.empty()) {
        lis.insert({act,1});
        elevados[pos] = 1;
    }
    else {

        it = lis.upper_bound({act,LIM+2});
        if (it == lis.end()) nuevo = {act,1};
        else nuevo = {act, (*it).val + 1};

        gf = false;
        do {
            if (it == lis.begin()) break;
            else {
                it--;
                if (gf) lis.erase(pas);
                gf =true;
                pas=it;
            }

            if ( (*it).val > nuevo.val) break;

        } while (true);

        lis.insert(nuevo);
        elevados[pos] = nuevo.val;
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //leer
    cin >> n >> x;
    rep(i,1,n) cin >> arr[i];

    // LIS al reves y asignar valores a cada i
    repa(i,n,1) LISa(arr[i],i);

    // lis hacia enfrente, checar primero y luego agregar al LIS
    lis.clear();
    rep(i,1,n) {

        num = arr[i] + x;

        if (i > 1) {

            it = lis.upper_bound({num-1,LIM+2});
            if (it != lis.begin()) {
                it--;
                a = (*it).val;
            }
            else a = 0;

        }
        else a = 0;

        a += elevados[i];
        if (a > res) res = a;


        LIS(arr[i],i);

    }

    //Imprimir
    cout << res;
}

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