oj.uz

Submission #257534

# Submission time Handle Problem Language Result Execution time Memory
257534 2020-08-04T11:37:12 Z anonymous Global Warming (CEOI18_glo) C++14
45 / 100
 1040 ms 262148 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[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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Runtime error 172 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 108484 KB Output is correct
2 Correct 1040 ms 110404 KB Output is correct
3 Correct 956 ms 110456 KB Output is correct
4 Correct 974 ms 110568 KB Output is correct
5 Correct 443 ms 60280 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 37880 KB Output is correct
2 Correct 201 ms 38212 KB Output is correct
3 Correct 204 ms 38136 KB Output is correct
4 Correct 109 ms 20472 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 99 ms 4164 KB Output is correct
7 Correct 153 ms 27384 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 378 ms 262144 KB Execution killed with signal 9 (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 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Runtime error 172 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -