Submission #442990

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442990	2021-07-09T13:00:16 Z	Focutai	Global Warming (CEOI18_glo)	C++17	45 / 100	654 ms	262144 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*100];
	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=(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=(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

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	235092 KB	Output is correct
2	Correct	100 ms	235032 KB	Output is correct
3	Correct	101 ms	235040 KB	Output is correct
4	Correct	101 ms	235052 KB	Output is correct
5	Correct	101 ms	235040 KB	Output is correct
6	Correct	119 ms	235032 KB	Output is correct
7	Correct	102 ms	235184 KB	Output is correct
8	Correct	103 ms	235092 KB	Output is correct
9	Correct	102 ms	235208 KB	Output is correct
10	Correct	103 ms	235120 KB	Output is correct
11	Correct	102 ms	235092 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	235092 KB	Output is correct
2	Correct	100 ms	235032 KB	Output is correct
3	Correct	101 ms	235040 KB	Output is correct
4	Correct	101 ms	235052 KB	Output is correct
5	Correct	101 ms	235040 KB	Output is correct
6	Correct	119 ms	235032 KB	Output is correct
7	Correct	102 ms	235184 KB	Output is correct
8	Correct	103 ms	235092 KB	Output is correct
9	Correct	102 ms	235208 KB	Output is correct
10	Correct	103 ms	235120 KB	Output is correct
11	Correct	102 ms	235092 KB	Output is correct
12	Correct	105 ms	235012 KB	Output is correct
13	Correct	102 ms	235076 KB	Output is correct
14	Correct	102 ms	235012 KB	Output is correct
15	Correct	102 ms	235044 KB	Output is correct
16	Correct	102 ms	235076 KB	Output is correct
17	Correct	104 ms	235124 KB	Output is correct
18	Correct	101 ms	235036 KB	Output is correct

Subtask #3
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	235092 KB	Output is correct
2	Correct	100 ms	235032 KB	Output is correct
3	Correct	101 ms	235040 KB	Output is correct
4	Correct	101 ms	235052 KB	Output is correct
5	Correct	101 ms	235040 KB	Output is correct
6	Correct	119 ms	235032 KB	Output is correct
7	Correct	102 ms	235184 KB	Output is correct
8	Correct	103 ms	235092 KB	Output is correct
9	Correct	102 ms	235208 KB	Output is correct
10	Correct	103 ms	235120 KB	Output is correct
11	Correct	102 ms	235092 KB	Output is correct
12	Correct	105 ms	235012 KB	Output is correct
13	Correct	102 ms	235076 KB	Output is correct
14	Correct	102 ms	235012 KB	Output is correct
15	Correct	102 ms	235044 KB	Output is correct
16	Correct	102 ms	235076 KB	Output is correct
17	Correct	104 ms	235124 KB	Output is correct
18	Correct	101 ms	235036 KB	Output is correct
19	Runtime error	570 ms	262144 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	492 ms	236668 KB	Output is correct
2	Correct	474 ms	236568 KB	Output is correct
3	Correct	455 ms	236680 KB	Output is correct
4	Correct	486 ms	236672 KB	Output is correct
5	Correct	313 ms	237752 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	177 ms	235544 KB	Output is correct
2	Correct	214 ms	235516 KB	Output is correct
3	Correct	174 ms	235512 KB	Output is correct
4	Correct	183 ms	235460 KB	Output is correct
5	Correct	107 ms	235120 KB	Output is correct
6	Correct	153 ms	235444 KB	Output is correct
7	Correct	173 ms	235572 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	654 ms	262144 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	235092 KB	Output is correct
2	Correct	100 ms	235032 KB	Output is correct
3	Correct	101 ms	235040 KB	Output is correct
4	Correct	101 ms	235052 KB	Output is correct
5	Correct	101 ms	235040 KB	Output is correct
6	Correct	119 ms	235032 KB	Output is correct
7	Correct	102 ms	235184 KB	Output is correct
8	Correct	103 ms	235092 KB	Output is correct
9	Correct	102 ms	235208 KB	Output is correct
10	Correct	103 ms	235120 KB	Output is correct
11	Correct	102 ms	235092 KB	Output is correct
12	Correct	105 ms	235012 KB	Output is correct
13	Correct	102 ms	235076 KB	Output is correct
14	Correct	102 ms	235012 KB	Output is correct
15	Correct	102 ms	235044 KB	Output is correct
16	Correct	102 ms	235076 KB	Output is correct
17	Correct	104 ms	235124 KB	Output is correct
18	Correct	101 ms	235036 KB	Output is correct
19	Runtime error	570 ms	262144 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-

Submission #442990

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 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
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