답안 #442995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442995	2021-07-09T13:05:11 Z	Focutai	Global Warming (CEOI18_glo)	C++17	100 / 100	420 ms	78952 KB

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf ((int)2e9)
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
int max(int x,int y,int z) {return max(max(x,y),z);}
#define N 200005
struct SMT
{
	struct Node
	{
		int ls,rs,val;
	};
	Node t[N*32];
	int cnt=1;
	void update(int &u,int l,int r,int L,int R,int v)
	{
		if(L>R) return ;
		if(!u) u=++cnt;
		if(L<=l&&r<=R) {t[u].val=max(t[u].val,v); return ;}
		int mid=((ll)l+r)/2;
		if(mid>=L) update(t[u].ls,l,mid,L,R,v);
		if(mid<R) update(t[u].rs,mid+1,r,L,R,v);
	}
	int query(int u,int l,int r,int pos)
	{
		if(!u) return 0;
		int ans=t[u].val,mid=((ll)l+r)/2;
		if(pos<=mid) ans=max(ans,query(t[u].ls,l,mid,pos));
		else ans=max(ans,query(t[u].rs,mid+1,r,pos));
		return ans;
	}
	void clear() {memset(t,0,sizeof(t)),cnt=1;}
}smt;
int a[N],f[N],n,d,rt=1;
signed main()
{
	cin>>n>>d;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++)
	{
		f[i]=smt.query(1,1,inf,a[i])+1;
		smt.update(rt,1,inf,a[i]+1,inf,f[i]);
	}
//	for(int i=1;i<=n;i++) printf("%d%c",f[i]," \n"[i==n]);
	smt.clear(); int ans=0;
	for(int i=n;i>=1;i--)
	{
		int res=smt.query(1,1,inf,a[i]+d);
		smt.update(rt,1,inf,1,a[i]+d-1,res+1);
//		printf("%d : %d %d\n",i,f[i-1],smt.query(rt,1,inf,a[i-1]+1));
		ans=max(ans,f[i-1]+smt.query(rt,1,inf,a[i-1]));
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	75340 KB	Output is correct
2	Correct	32 ms	75400 KB	Output is correct
3	Correct	34 ms	75352 KB	Output is correct
4	Correct	33 ms	75312 KB	Output is correct
5	Correct	33 ms	75364 KB	Output is correct
6	Correct	34 ms	75380 KB	Output is correct
7	Correct	33 ms	75332 KB	Output is correct
8	Correct	33 ms	75432 KB	Output is correct
9	Correct	33 ms	75424 KB	Output is correct
10	Correct	34 ms	75400 KB	Output is correct
11	Correct	33 ms	75432 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	75340 KB	Output is correct
2	Correct	32 ms	75400 KB	Output is correct
3	Correct	34 ms	75352 KB	Output is correct
4	Correct	33 ms	75312 KB	Output is correct
5	Correct	33 ms	75364 KB	Output is correct
6	Correct	34 ms	75380 KB	Output is correct
7	Correct	33 ms	75332 KB	Output is correct
8	Correct	33 ms	75432 KB	Output is correct
9	Correct	33 ms	75424 KB	Output is correct
10	Correct	34 ms	75400 KB	Output is correct
11	Correct	33 ms	75432 KB	Output is correct
12	Correct	31 ms	75344 KB	Output is correct
13	Correct	37 ms	75352 KB	Output is correct
14	Correct	34 ms	75328 KB	Output is correct
15	Correct	33 ms	75320 KB	Output is correct
16	Correct	34 ms	75332 KB	Output is correct
17	Correct	38 ms	75332 KB	Output is correct
18	Correct	35 ms	75316 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	75340 KB	Output is correct
2	Correct	32 ms	75400 KB	Output is correct
3	Correct	34 ms	75352 KB	Output is correct
4	Correct	33 ms	75312 KB	Output is correct
5	Correct	33 ms	75364 KB	Output is correct
6	Correct	34 ms	75380 KB	Output is correct
7	Correct	33 ms	75332 KB	Output is correct
8	Correct	33 ms	75432 KB	Output is correct
9	Correct	33 ms	75424 KB	Output is correct
10	Correct	34 ms	75400 KB	Output is correct
11	Correct	33 ms	75432 KB	Output is correct
12	Correct	31 ms	75344 KB	Output is correct
13	Correct	37 ms	75352 KB	Output is correct
14	Correct	34 ms	75328 KB	Output is correct
15	Correct	33 ms	75320 KB	Output is correct
16	Correct	34 ms	75332 KB	Output is correct
17	Correct	38 ms	75332 KB	Output is correct
18	Correct	35 ms	75316 KB	Output is correct
19	Correct	35 ms	75368 KB	Output is correct
20	Correct	34 ms	75416 KB	Output is correct
21	Correct	34 ms	75328 KB	Output is correct
22	Correct	35 ms	75340 KB	Output is correct
23	Correct	34 ms	75352 KB	Output is correct
24	Correct	34 ms	75356 KB	Output is correct
25	Correct	34 ms	75340 KB	Output is correct
26	Correct	35 ms	75428 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	396 ms	76984 KB	Output is correct
2	Correct	420 ms	76932 KB	Output is correct
3	Correct	392 ms	76984 KB	Output is correct
4	Correct	399 ms	77000 KB	Output is correct
5	Correct	262 ms	76996 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	75756 KB	Output is correct
2	Correct	114 ms	75716 KB	Output is correct
3	Correct	149 ms	75840 KB	Output is correct
4	Correct	94 ms	75840 KB	Output is correct
5	Correct	34 ms	75324 KB	Output is correct
6	Correct	89 ms	75808 KB	Output is correct
7	Correct	95 ms	75816 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	188 ms	76320 KB	Output is correct
2	Correct	191 ms	77172 KB	Output is correct
3	Correct	379 ms	78916 KB	Output is correct
4	Correct	228 ms	78200 KB	Output is correct
5	Correct	132 ms	76776 KB	Output is correct
6	Correct	226 ms	78104 KB	Output is correct
7	Correct	203 ms	78720 KB	Output is correct
8	Correct	186 ms	77108 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	75340 KB	Output is correct
2	Correct	32 ms	75400 KB	Output is correct
3	Correct	34 ms	75352 KB	Output is correct
4	Correct	33 ms	75312 KB	Output is correct
5	Correct	33 ms	75364 KB	Output is correct
6	Correct	34 ms	75380 KB	Output is correct
7	Correct	33 ms	75332 KB	Output is correct
8	Correct	33 ms	75432 KB	Output is correct
9	Correct	33 ms	75424 KB	Output is correct
10	Correct	34 ms	75400 KB	Output is correct
11	Correct	33 ms	75432 KB	Output is correct
12	Correct	31 ms	75344 KB	Output is correct
13	Correct	37 ms	75352 KB	Output is correct
14	Correct	34 ms	75328 KB	Output is correct
15	Correct	33 ms	75320 KB	Output is correct
16	Correct	34 ms	75332 KB	Output is correct
17	Correct	38 ms	75332 KB	Output is correct
18	Correct	35 ms	75316 KB	Output is correct
19	Correct	35 ms	75368 KB	Output is correct
20	Correct	34 ms	75416 KB	Output is correct
21	Correct	34 ms	75328 KB	Output is correct
22	Correct	35 ms	75340 KB	Output is correct
23	Correct	34 ms	75352 KB	Output is correct
24	Correct	34 ms	75356 KB	Output is correct
25	Correct	34 ms	75340 KB	Output is correct
26	Correct	35 ms	75428 KB	Output is correct
27	Correct	396 ms	76984 KB	Output is correct
28	Correct	420 ms	76932 KB	Output is correct
29	Correct	392 ms	76984 KB	Output is correct
30	Correct	399 ms	77000 KB	Output is correct
31	Correct	262 ms	76996 KB	Output is correct
32	Correct	112 ms	75756 KB	Output is correct
33	Correct	114 ms	75716 KB	Output is correct
34	Correct	149 ms	75840 KB	Output is correct
35	Correct	94 ms	75840 KB	Output is correct
36	Correct	34 ms	75324 KB	Output is correct
37	Correct	89 ms	75808 KB	Output is correct
38	Correct	95 ms	75816 KB	Output is correct
39	Correct	188 ms	76320 KB	Output is correct
40	Correct	191 ms	77172 KB	Output is correct
41	Correct	379 ms	78916 KB	Output is correct
42	Correct	228 ms	78200 KB	Output is correct
43	Correct	132 ms	76776 KB	Output is correct
44	Correct	226 ms	78104 KB	Output is correct
45	Correct	203 ms	78720 KB	Output is correct
46	Correct	186 ms	77108 KB	Output is correct
47	Correct	193 ms	77184 KB	Output is correct
48	Correct	232 ms	77176 KB	Output is correct
49	Correct	417 ms	78948 KB	Output is correct
50	Correct	257 ms	78188 KB	Output is correct
51	Correct	194 ms	77360 KB	Output is correct
52	Correct	255 ms	78224 KB	Output is correct
53	Correct	225 ms	78296 KB	Output is correct
54	Correct	217 ms	78924 KB	Output is correct
55	Correct	307 ms	78952 KB	Output is correct

답안 #442995

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