oj.uz

Submission #257526

# Submission time Handle Problem Language Result Execution time Memory
257526 2020-08-04T11:31:46 Z anonymous Global Warming (CEOI18_glo) C++14
0 / 100
 59 ms 3960 KB 
#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[A[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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 2292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -