Submission #257534

#	Time	Username	Problem	Language	Result	Execution time	Memory
257534		anonymous	Global Warming (CEOI18_glo)	C++14	45 / 100	1040 ms	262148 KiB

glo

#include <iostream>
#include <map>
#define MAXN 200005
using namespace std;
int N, X, Ans, A[MAXN], Prev[MAXN];
map <int,int> Cur;
class LazyCreate {
    int ST[MAXN * 120][3]; //prefix best, suffix best, best match, left child, right child
    int L[MAXN * 120], R[MAXN * 120], pt = 2;
    void pushup(int cur) {
        ST[cur][0] = max(ST[L[cur]][0], ST[R[cur]][0]);
        ST[cur][1] = max(ST[L[cur]][1], ST[R[cur]][1]);
        ST[cur][2] = max(ST[L[cur]][2], ST[R[cur]][2]);
        ST[cur][2] = max(ST[cur][2], ST[L[cur]][0] + ST[R[cur]][1]);
    }
    void addnodes(int par) {
        L[par] = pt++;
        R[par] = pt++;
    }
public:
    void upd(bool b, int val, int ind, int l, int r, int cur) {
        if (ind < l || ind > r) {return;}
        if (l == r) {
            ST[cur][b] = val;
        } else {
            if (!L[cur]) {addnodes(cur);}
            int mid = (l + r) >> 1;
            upd(b, val, ind, l, mid, L[cur]);
            upd(b, val, ind, mid+1, r, R[cur]);
            pushup(cur);
        }
    }
    int ask(bool b, int lo, int hi, int l, int r, int cur) {
        if (lo > r || hi < l || !cur) {return(0);}
        if (lo <= l && hi >= r) {return(ST[cur][b]);}
        int mid = (l + r) >> 1;
        return(max(ask(b,lo, hi, l, mid, L[cur]),
                   ask(b,lo, hi, mid+1, r, R[cur])));
    }
    int get() {return(ST[1][2]);}
} ST;

int main() {
    //freopen("gloin.txt","r",stdin);
    scanf("%d %d",&N,&X);
    for (int i=1; i<=N; i++) {
        scanf("%d",&A[i]);
    }

    for (int i=1; i <= N; i++) {
        Prev[i] = Cur[A[i]];
        Cur[A[i]] = ST.ask(0, 0,  A[i]-1, 0, 2e9, 1)+1;
        ST.upd(0, Cur[A[i]], A[i], 0, 2e9, 1);
    }

    for (int i=N; i >= 1; i--) {
        Ans = max(Ans, ST.get());
        ST.upd(1, ST.ask(1,A[i]+X+1, 2e9, 0, 2e9, 1)+1, A[i]+X, 0, 2e9, 1);
        ST.upd(0, Prev[i], A[i], 0, 2e9, 1);
    }

    printf("%d", Ans);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:45: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:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~

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