답안 #160060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160060	2019-10-25T20:43:56 Z	Rouge_Hugo	Global Warming (CEOI18_glo)	C++14	100 / 100	1272 ms	57096 KB

#include <bits/stdc++.h>

using namespace std;
long long  n,x;
const long long  N=200009;
map<long long,long long>m;
int  tree[11*N],tree1[11*N],a[N];
void update(int ind,int st,int end,int uind,int uval)
{
    if (st==end)
    {
        tree[ind]=max(tree[ind],uval);
        return ;
    }
    int m=(st+end)/2;
    if (uind>m)update(ind*2+2,m+1,end,uind,uval);
    else update(ind*2+1,st,m,uind,uval);
    tree[ind]=max(tree[ind*2+1],tree[ind*2+2]);
}

void update1(int ind,int st,int end,int uind,int uval)
{
    if (st==end)
    {
        tree1[ind]=max(tree1[ind],uval);
        return ;
    }
    int m=(st+end)/2;
    if (uind>m)update1(ind*2+2,m+1,end,uind,uval);
    else update1(ind*2+1,st,m,uind,uval);
    tree1[ind]=max(tree1[ind*2+1],tree1[ind*2+2]);
}
int query(int ind,int st,int end,int l,int r)
{
    if (l<=st&&end<=r)return tree[ind];
    if (l>end||r<st)return 0;
    int m=(st+end )/2;
    return max(query(ind*2+1,st,m,l,r),query(ind*2+2,m+1,end,l,r));

}

int query1(int ind,int st,int end,int l,int r)
{
    if (l<=st&&end<=r)return tree1[ind];
    if (l>end||r<st)return 0;
    int  m=(st+end )/2;
    return max(query1(ind*2+1,st,m,l,r),query1(ind*2+2,m+1,end,l,r));
}
int main()
{ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

    cin>>n>>x;
    for(int  i=0;i<n;i++){
        cin>>a[i];
        m[a[i]-1]++;
        m[a[i]]++;
        m[a[i]+x-1]++;
    }
    long long  re=0;
    for(auto it:m)
    {
        m[it.first]=re++;
    }
    int  mx=0;
    for(int  i=0;i<n;i++)
    {
        int   xx=query(0,0,re,0,m[a[i]-1]);

        int  y=query(0,0,re,0,m[a[i]+x-1]);
        update(0,0,re,m[a[i]],xx+1);

        y=max(query1(0,0,re,0,m[a[i]-1]),y);
        update1(0,0,re,m[a[i]],y+1);
        mx=max(mx,y+1);
        mx=max(mx,xx+1);
        //cout<<xx<<" "<<y<<endl;
    }
    cout<<mx;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	993 ms	34456 KB	Output is correct
2	Correct	991 ms	34500 KB	Output is correct
3	Correct	966 ms	34668 KB	Output is correct
4	Correct	944 ms	34500 KB	Output is correct
5	Correct	505 ms	17740 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	14072 KB	Output is correct
2	Correct	224 ms	14684 KB	Output is correct
3	Correct	237 ms	14588 KB	Output is correct
4	Correct	215 ms	7672 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	125 ms	4988 KB	Output is correct
7	Correct	162 ms	10368 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	540 ms	25080 KB	Output is correct
2	Correct	586 ms	25208 KB	Output is correct
3	Correct	1272 ms	49912 KB	Output is correct
4	Correct	539 ms	25424 KB	Output is correct
5	Correct	351 ms	15352 KB	Output is correct
6	Correct	653 ms	29108 KB	Output is correct
7	Correct	666 ms	29052 KB	Output is correct
8	Correct	469 ms	22624 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	388 KB	Output is correct
19	Correct	4 ms	632 KB	Output is correct
20	Correct	4 ms	632 KB	Output is correct
21	Correct	4 ms	684 KB	Output is correct
22	Correct	4 ms	504 KB	Output is correct
23	Correct	3 ms	504 KB	Output is correct
24	Correct	3 ms	504 KB	Output is correct
25	Correct	3 ms	376 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Correct	993 ms	34456 KB	Output is correct
28	Correct	991 ms	34500 KB	Output is correct
29	Correct	966 ms	34668 KB	Output is correct
30	Correct	944 ms	34500 KB	Output is correct
31	Correct	505 ms	17740 KB	Output is correct
32	Correct	221 ms	14072 KB	Output is correct
33	Correct	224 ms	14684 KB	Output is correct
34	Correct	237 ms	14588 KB	Output is correct
35	Correct	215 ms	7672 KB	Output is correct
36	Correct	2 ms	376 KB	Output is correct
37	Correct	125 ms	4988 KB	Output is correct
38	Correct	162 ms	10368 KB	Output is correct
39	Correct	540 ms	25080 KB	Output is correct
40	Correct	586 ms	25208 KB	Output is correct
41	Correct	1272 ms	49912 KB	Output is correct
42	Correct	539 ms	25424 KB	Output is correct
43	Correct	351 ms	15352 KB	Output is correct
44	Correct	653 ms	29108 KB	Output is correct
45	Correct	666 ms	29052 KB	Output is correct
46	Correct	469 ms	22624 KB	Output is correct
47	Correct	531 ms	28792 KB	Output is correct
48	Correct	536 ms	28776 KB	Output is correct
49	Correct	1262 ms	57096 KB	Output is correct
50	Correct	399 ms	29348 KB	Output is correct
51	Correct	410 ms	14000 KB	Output is correct
52	Correct	576 ms	19192 KB	Output is correct
53	Correct	689 ms	31608 KB	Output is correct
54	Correct	766 ms	32508 KB	Output is correct
55	Correct	822 ms	40712 KB	Output is correct

답안 #160060

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