답안 #907238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
907238	2024-01-15T09:57:44 Z	heeheeheehaaw	Global Warming (CEOI18_glo)	C++17	100 / 100	725 ms	41888 KB

#include <bits/stdc++.h>

using namespace std;

map<int, int> mp1, mp2;
int cnt = 0;
int v[200005];
int aib1[400005], aib2[400005];

void upd1(int poz, int val)
{
    for(int i = poz; i <= cnt; i += (i & (-i)))
        aib1[i] = max(aib1[i], val);
    return;
}

int qry1(int poz)
{
    int maxx = 0;
    for(int i = poz; i >= 1; i -= (i & (-i)))
        maxx = max(maxx, aib1[i]);
    return maxx;
}

void upd2(int poz, int val)
{
    for(int i = poz; i <= cnt; i += (i & (-i)))
        aib2[i] = max(aib2[i], val);
    return;
}

int qry2(int poz)
{
    int maxx = 0;
    for(int i = poz; i >= 1; i -= (i & (-i)))
        maxx = max(maxx, aib2[i]);
    return maxx;
}

signed main()
{
    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
        cin>>v[i], mp1[v[i]] = 1, mp1[v[i] - k] = 1;
    for(auto it : mp1)
        mp2[it.first] = ++cnt;
    for(int i = 1; i <= n; i++)
    {
        upd2(mp2[v[i]], qry2(mp2[v[i]] - 1) + 1);
        upd2(mp2[v[i]], qry1(mp2[v[i]] - 1) + 1);
        upd1(mp2[v[i] - k], qry1(mp2[v[i] - k] - 1) + 1);
    }

    cout<<qry2(cnt);
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	2 ms	544 KB	Output is correct
20	Correct	2 ms	604 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	2 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	407 ms	21560 KB	Output is correct
2	Correct	382 ms	21488 KB	Output is correct
3	Correct	388 ms	21584 KB	Output is correct
4	Correct	403 ms	21328 KB	Output is correct
5	Correct	157 ms	11596 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	10576 KB	Output is correct
2	Correct	96 ms	10700 KB	Output is correct
3	Correct	93 ms	10804 KB	Output is correct
4	Correct	40 ms	5716 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	45 ms	5520 KB	Output is correct
7	Correct	75 ms	9108 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	265 ms	20408 KB	Output is correct
2	Correct	260 ms	20564 KB	Output is correct
3	Correct	725 ms	40480 KB	Output is correct
4	Correct	230 ms	20724 KB	Output is correct
5	Correct	163 ms	20228 KB	Output is correct
6	Correct	317 ms	38160 KB	Output is correct
7	Correct	328 ms	38228 KB	Output is correct
8	Correct	225 ms	20172 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	2 ms	544 KB	Output is correct
20	Correct	2 ms	604 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	2 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	407 ms	21560 KB	Output is correct
28	Correct	382 ms	21488 KB	Output is correct
29	Correct	388 ms	21584 KB	Output is correct
30	Correct	403 ms	21328 KB	Output is correct
31	Correct	157 ms	11596 KB	Output is correct
32	Correct	93 ms	10576 KB	Output is correct
33	Correct	96 ms	10700 KB	Output is correct
34	Correct	93 ms	10804 KB	Output is correct
35	Correct	40 ms	5716 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	45 ms	5520 KB	Output is correct
38	Correct	75 ms	9108 KB	Output is correct
39	Correct	265 ms	20408 KB	Output is correct
40	Correct	260 ms	20564 KB	Output is correct
41	Correct	725 ms	40480 KB	Output is correct
42	Correct	230 ms	20724 KB	Output is correct
43	Correct	163 ms	20228 KB	Output is correct
44	Correct	317 ms	38160 KB	Output is correct
45	Correct	328 ms	38228 KB	Output is correct
46	Correct	225 ms	20172 KB	Output is correct
47	Correct	225 ms	21156 KB	Output is correct
48	Correct	240 ms	20984 KB	Output is correct
49	Correct	560 ms	41888 KB	Output is correct
50	Correct	205 ms	21400 KB	Output is correct
51	Correct	172 ms	15700 KB	Output is correct
52	Correct	251 ms	21588 KB	Output is correct
53	Correct	340 ms	40532 KB	Output is correct
54	Correct	354 ms	40140 KB	Output is correct
55	Correct	395 ms	35196 KB	Output is correct

답안 #907238

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 25.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
25.0 / 25.0