Submission #88463

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
88463	2018-12-06T03:08:58 Z	tieunhi	Global Warming (CEOI18_glo)	C++14	58 / 100	166 ms	16032 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];
    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	1144 KB	Output is correct
2	Correct	3 ms	1276 KB	Output is correct
3	Correct	3 ms	1276 KB	Output is correct
4	Correct	3 ms	1296 KB	Output is correct
5	Correct	3 ms	1468 KB	Output is correct
6	Correct	2 ms	1468 KB	Output is correct
7	Correct	3 ms	1468 KB	Output is correct
8	Correct	3 ms	1468 KB	Output is correct
9	Correct	2 ms	1468 KB	Output is correct
10	Correct	3 ms	1512 KB	Output is correct
11	Correct	3 ms	1512 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1144 KB	Output is correct
2	Correct	3 ms	1276 KB	Output is correct
3	Correct	3 ms	1276 KB	Output is correct
4	Correct	3 ms	1296 KB	Output is correct
5	Correct	3 ms	1468 KB	Output is correct
6	Correct	2 ms	1468 KB	Output is correct
7	Correct	3 ms	1468 KB	Output is correct
8	Correct	3 ms	1468 KB	Output is correct
9	Correct	2 ms	1468 KB	Output is correct
10	Correct	3 ms	1512 KB	Output is correct
11	Correct	3 ms	1512 KB	Output is correct
12	Correct	3 ms	1512 KB	Output is correct
13	Correct	3 ms	1512 KB	Output is correct
14	Correct	3 ms	1512 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	3 ms	1528 KB	Output is correct
17	Correct	3 ms	1528 KB	Output is correct
18	Correct	3 ms	1528 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1144 KB	Output is correct
2	Correct	3 ms	1276 KB	Output is correct
3	Correct	3 ms	1276 KB	Output is correct
4	Correct	3 ms	1296 KB	Output is correct
5	Correct	3 ms	1468 KB	Output is correct
6	Correct	2 ms	1468 KB	Output is correct
7	Correct	3 ms	1468 KB	Output is correct
8	Correct	3 ms	1468 KB	Output is correct
9	Correct	2 ms	1468 KB	Output is correct
10	Correct	3 ms	1512 KB	Output is correct
11	Correct	3 ms	1512 KB	Output is correct
12	Correct	3 ms	1512 KB	Output is correct
13	Correct	3 ms	1512 KB	Output is correct
14	Correct	3 ms	1512 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	3 ms	1528 KB	Output is correct
17	Correct	3 ms	1528 KB	Output is correct
18	Correct	3 ms	1528 KB	Output is correct
19	Correct	3 ms	1528 KB	Output is correct
20	Correct	3 ms	1528 KB	Output is correct
21	Correct	3 ms	1528 KB	Output is correct
22	Correct	3 ms	1528 KB	Output is correct
23	Correct	3 ms	1528 KB	Output is correct
24	Correct	3 ms	1528 KB	Output is correct
25	Correct	3 ms	1528 KB	Output is correct
26	Correct	3 ms	1528 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	6140 KB	Output is correct
2	Correct	147 ms	8048 KB	Output is correct
3	Correct	151 ms	10084 KB	Output is correct
4	Correct	151 ms	12040 KB	Output is correct
5	Correct	79 ms	13180 KB	Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	13180 KB	Output is correct
2	Correct	78 ms	13180 KB	Output is correct
3	Incorrect	166 ms	16032 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1144 KB	Output is correct
2	Correct	3 ms	1276 KB	Output is correct
3	Correct	3 ms	1276 KB	Output is correct
4	Correct	3 ms	1296 KB	Output is correct
5	Correct	3 ms	1468 KB	Output is correct
6	Correct	2 ms	1468 KB	Output is correct
7	Correct	3 ms	1468 KB	Output is correct
8	Correct	3 ms	1468 KB	Output is correct
9	Correct	2 ms	1468 KB	Output is correct
10	Correct	3 ms	1512 KB	Output is correct
11	Correct	3 ms	1512 KB	Output is correct
12	Correct	3 ms	1512 KB	Output is correct
13	Correct	3 ms	1512 KB	Output is correct
14	Correct	3 ms	1512 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	3 ms	1528 KB	Output is correct
17	Correct	3 ms	1528 KB	Output is correct
18	Correct	3 ms	1528 KB	Output is correct
19	Correct	3 ms	1528 KB	Output is correct
20	Correct	3 ms	1528 KB	Output is correct
21	Correct	3 ms	1528 KB	Output is correct
22	Correct	3 ms	1528 KB	Output is correct
23	Correct	3 ms	1528 KB	Output is correct
24	Correct	3 ms	1528 KB	Output is correct
25	Correct	3 ms	1528 KB	Output is correct
26	Correct	3 ms	1528 KB	Output is correct
27	Correct	150 ms	6140 KB	Output is correct
28	Correct	147 ms	8048 KB	Output is correct
29	Correct	151 ms	10084 KB	Output is correct
30	Correct	151 ms	12040 KB	Output is correct
31	Correct	79 ms	13180 KB	Output is correct
32	Correct	37 ms	13180 KB	Output is correct
33	Correct	38 ms	13180 KB	Output is correct
34	Correct	40 ms	13180 KB	Output is correct
35	Correct	21 ms	13180 KB	Output is correct
36	Correct	2 ms	13180 KB	Output is correct
37	Correct	19 ms	13180 KB	Output is correct
38	Correct	32 ms	13180 KB	Output is correct
39	Correct	77 ms	13180 KB	Output is correct
40	Correct	78 ms	13180 KB	Output is correct
41	Incorrect	166 ms	16032 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Submission #88463

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

Subtask #7
0 / 25.0