Submission #162076

#	Time	Username	Problem	Language	Result	Execution time	Memory
162076		Akashi	Global Warming (CEOI18_glo)	C++14	100 / 100	709 ms	158968 KiB

glo

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

int n, x;
int a[200005], s[200005];
int suf[200005], pref[200005];

int Sol = 0;

void find_lis(int d[], int st, int dr, int sgn){
    int L = 0;
    memset(s, 0, sizeof(s));

    for(int i = st; i != dr ; i += sgn){
        a[i] = a[i] * sgn;

        if(s[L] < a[i] || L == 0){
            s[++L] = a[i];
            d[i] = L;
        }
        else{
            int l = 1, dr = L;
            bool ok = true;
            while(l <= dr){
                int mij = (l + dr) / 2;

                if(s[mij] == a[i]){
                    ok = false;
                    d[i] = mij;
                    break ;
                }

                if(s[mij] > a[i]) dr = mij - 1;
                else l = mij + 1;
            }

            if(s[dr] == a[i]){
                ok = false;
                d[i] = dr;
            }

            if(!ok) continue ;

            s[l] = a[i], d[i] = l;
        }
    }

    Sol = max(Sol, L);

    for(int i = 1; i <= n ; ++i) a[i] = a[i] * sgn;
}

struct node{
    int val;
    node *left, *right;

    node(){
        val = 0;
        left = right = 0;
    }
};

node *arb;

int query(int x, int y, int st = 1, int dr = 1e9, node *nod = arb){
    if(nod == NULL) return 0;
    if(x <= st && dr <= y) return nod->val;

    int mij = (st + dr) / 2;
    int a1 = 0, a2 = 0;
    if(x <= mij) a1 = query(x, y, st, mij, nod->left);
    if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod->right);

    return max(a1, a2);
}

void update(int val, int pos, int st = 1, int dr = 1e9, node *nod = arb){
    if(st == dr){
        nod->val = val;
        return ;
    }

    if(nod->left == NULL) nod->left = new node;
    if(nod->right == NULL) nod->right = new node;

    int mij = (st + dr) / 2;
    if(pos <= mij){
        update(val, pos, st, mij, nod->left);
    }
    else{
        update(val, pos, mij + 1, dr, nod->right);
    }

    nod->val = max(nod->left->val, nod->right->val);
}

void build(int st = 1, int dr = 1e9, node *nod = arb){
    if(nod == NULL) return ;
    if(st == dr){
        nod->val = 0;
        return ;
    }

    int mij = (st + dr) / 2;
    build(st, mij, nod->left);
    build(mij + 1, dr, nod->right);

    nod->val = 0;
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &x);

    for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);

    find_lis(pref, 1, n + 1, 1);
    find_lis(suf, n, 0, -1);

    if(x == 0){
        printf("%d", Sol);
        return 0;
    }

    arb = new node;
    update(pref[1], a[1]);
    for(int i = 1; i < n ; ++i){
        int aux = suf[i + 1];
        aux = aux + query(max(a[i + 1] - x + 1, 1), min(a[i + 1] + x - 1, 1000000000));
        Sol = max(Sol, aux);

        update(pref[i + 1], a[i + 1]);
    }

    printf("%d", Sol);

    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &x);
     ~~~~~^~~~~~~~~~~~~~~~
glo.cpp:117:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~

• 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