Submission #88464

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
88464	2018-12-06T03:10:19 Z	tieunhi	Global Warming (CEOI18_glo)	C++14	75 / 100	171 ms	15840 KB

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define N 200005
#define maxc 1ll*100000000000000007
#define ll long long

using namespace std;

int n, d, a[N], b[N], rr[N*2], cur, rig[N];
struct BIT
{
    int t[N*2];
    void reset()
    {
        memset(t, 0, sizeof t);
    }
    void upd(int x, int val)
    {
        for (; x < N; x += (x & -x)) t[x] = max(t[x], val);
    }
    int get(int x)
    {
        int ans = 0;
        for (; x; x -= (x & -x)) ans = max(ans, t[x]);
        return ans;
    }
}t;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> d;
    FOR(i, 1, n)
    {
        cin >> a[i];
        rr[++cur] = a[i];
        rr[++cur] = a[i] + d;
    }
    sort(rr+1, rr+cur+1);
    cur = unique(rr+1, rr+cur+1) - rr - 1;
    FOR(i, 1, n)
    {
        b[i] = lower_bound(rr+1, rr+cur+1, a[i]+d) - rr;
        a[i] = lower_bound(rr+1, rr+cur+1, a[i]) - rr;
    }
    FORD(i, n, 1)
    {
        rig[i] = t.get(cur - b[i]) + 1;
        t.upd(cur - b[i] + 1, rig[i]);
    }
    int res = rig[1];
    t.reset();
    FOR(i, 1, n)
    {
        res = max(res, t.get(b[i]-1) + rig[i]);
        int valLIS = t.get(a[i]-1) + 1;
        t.upd(a[i], valLIS);
    }
    cout <<res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1912 KB	Output is correct
2	Correct	3 ms	2080 KB	Output is correct
3	Correct	3 ms	2184 KB	Output is correct
4	Correct	3 ms	2184 KB	Output is correct
5	Correct	3 ms	2184 KB	Output is correct
6	Correct	3 ms	2184 KB	Output is correct
7	Correct	3 ms	2184 KB	Output is correct
8	Correct	3 ms	2184 KB	Output is correct
9	Correct	3 ms	2184 KB	Output is correct
10	Correct	3 ms	2184 KB	Output is correct
11	Correct	4 ms	2204 KB	Output is correct
12	Correct	3 ms	2204 KB	Output is correct
13	Correct	3 ms	2204 KB	Output is correct
14	Correct	3 ms	2204 KB	Output is correct
15	Correct	3 ms	2204 KB	Output is correct
16	Correct	4 ms	2204 KB	Output is correct
17	Correct	3 ms	2204 KB	Output is correct
18	Correct	3 ms	2204 KB	Output is correct
19	Correct	4 ms	2204 KB	Output is correct
20	Correct	4 ms	2204 KB	Output is correct
21	Correct	4 ms	2204 KB	Output is correct
22	Correct	4 ms	2204 KB	Output is correct
23	Correct	4 ms	2216 KB	Output is correct
24	Correct	4 ms	2216 KB	Output is correct
25	Correct	4 ms	2216 KB	Output is correct
26	Correct	4 ms	2216 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	152 ms	5996 KB	Output is correct
2	Correct	153 ms	6140 KB	Output is correct
3	Correct	148 ms	6140 KB	Output is correct
4	Correct	156 ms	6140 KB	Output is correct
5	Correct	77 ms	6152 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	6152 KB	Output is correct
2	Correct	38 ms	6152 KB	Output is correct
3	Correct	39 ms	6152 KB	Output is correct
4	Correct	21 ms	6152 KB	Output is correct
5	Correct	3 ms	6152 KB	Output is correct
6	Correct	19 ms	6152 KB	Output is correct
7	Correct	32 ms	6152 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	6152 KB	Output is correct
2	Correct	78 ms	6152 KB	Output is correct
3	Correct	171 ms	6152 KB	Output is correct
4	Correct	86 ms	7292 KB	Output is correct
5	Correct	48 ms	7292 KB	Output is correct
6	Correct	79 ms	8852 KB	Output is correct
7	Correct	87 ms	10872 KB	Output is correct
8	Correct	63 ms	10872 KB	Output is correct

Subtask #7
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1912 KB	Output is correct
2	Correct	3 ms	2080 KB	Output is correct
3	Correct	3 ms	2184 KB	Output is correct
4	Correct	3 ms	2184 KB	Output is correct
5	Correct	3 ms	2184 KB	Output is correct
6	Correct	3 ms	2184 KB	Output is correct
7	Correct	3 ms	2184 KB	Output is correct
8	Correct	3 ms	2184 KB	Output is correct
9	Correct	3 ms	2184 KB	Output is correct
10	Correct	3 ms	2184 KB	Output is correct
11	Correct	4 ms	2204 KB	Output is correct
12	Correct	3 ms	2204 KB	Output is correct
13	Correct	3 ms	2204 KB	Output is correct
14	Correct	3 ms	2204 KB	Output is correct
15	Correct	3 ms	2204 KB	Output is correct
16	Correct	4 ms	2204 KB	Output is correct
17	Correct	3 ms	2204 KB	Output is correct
18	Correct	3 ms	2204 KB	Output is correct
19	Correct	4 ms	2204 KB	Output is correct
20	Correct	4 ms	2204 KB	Output is correct
21	Correct	4 ms	2204 KB	Output is correct
22	Correct	4 ms	2204 KB	Output is correct
23	Correct	4 ms	2216 KB	Output is correct
24	Correct	4 ms	2216 KB	Output is correct
25	Correct	4 ms	2216 KB	Output is correct
26	Correct	4 ms	2216 KB	Output is correct
27	Correct	152 ms	5996 KB	Output is correct
28	Correct	153 ms	6140 KB	Output is correct
29	Correct	148 ms	6140 KB	Output is correct
30	Correct	156 ms	6140 KB	Output is correct
31	Correct	77 ms	6152 KB	Output is correct
32	Correct	38 ms	6152 KB	Output is correct
33	Correct	38 ms	6152 KB	Output is correct
34	Correct	39 ms	6152 KB	Output is correct
35	Correct	21 ms	6152 KB	Output is correct
36	Correct	3 ms	6152 KB	Output is correct
37	Correct	19 ms	6152 KB	Output is correct
38	Correct	32 ms	6152 KB	Output is correct
39	Correct	80 ms	6152 KB	Output is correct
40	Correct	78 ms	6152 KB	Output is correct
41	Correct	171 ms	6152 KB	Output is correct
42	Correct	86 ms	7292 KB	Output is correct
43	Correct	48 ms	7292 KB	Output is correct
44	Correct	79 ms	8852 KB	Output is correct
45	Correct	87 ms	10872 KB	Output is correct
46	Correct	63 ms	10872 KB	Output is correct
47	Correct	78 ms	11020 KB	Output is correct
48	Correct	77 ms	11956 KB	Output is correct
49	Incorrect	165 ms	15840 KB	Output isn't correct
50	Halted	0 ms	0 KB	-

Submission #88464

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
0 / 25.0