답안 #257534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #257534

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 0 / 17.0

Subtask #7 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
0 / 17.0

Subtask #7
0 / 25.0