oj.uz

답안 #442993

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442993 2021-07-09T13:02:21 Z Focutai Global Warming (CEOI18_glo) C++17
45 / 100
 730 ms 262152 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*110];
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 258500 KB Output is correct
2 Correct 111 ms 258612 KB Output is correct
3 Correct 112 ms 258588 KB Output is correct
4 Correct 118 ms 258492 KB Output is correct
5 Correct 116 ms 258500 KB Output is correct
6 Correct 114 ms 258556 KB Output is correct
7 Correct 110 ms 258568 KB Output is correct
8 Correct 110 ms 258568 KB Output is correct
9 Correct 109 ms 258576 KB Output is correct
10 Correct 113 ms 258520 KB Output is correct
11 Correct 110 ms 258608 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 258500 KB Output is correct
2 Correct 111 ms 258612 KB Output is correct
3 Correct 112 ms 258588 KB Output is correct
4 Correct 118 ms 258492 KB Output is correct
5 Correct 116 ms 258500 KB Output is correct
6 Correct 114 ms 258556 KB Output is correct
7 Correct 110 ms 258568 KB Output is correct
8 Correct 110 ms 258568 KB Output is correct
9 Correct 109 ms 258576 KB Output is correct
10 Correct 113 ms 258520 KB Output is correct
11 Correct 110 ms 258608 KB Output is correct
12 Correct 125 ms 258664 KB Output is correct
13 Correct 111 ms 258592 KB Output is correct
14 Correct 109 ms 258500 KB Output is correct
15 Correct 119 ms 258612 KB Output is correct
16 Correct 111 ms 258564 KB Output is correct
17 Correct 125 ms 258600 KB Output is correct
18 Correct 113 ms 258552 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 258500 KB Output is correct
2 Correct 111 ms 258612 KB Output is correct
3 Correct 112 ms 258588 KB Output is correct
4 Correct 118 ms 258492 KB Output is correct
5 Correct 116 ms 258500 KB Output is correct
6 Correct 114 ms 258556 KB Output is correct
7 Correct 110 ms 258568 KB Output is correct
8 Correct 110 ms 258568 KB Output is correct
9 Correct 109 ms 258576 KB Output is correct
10 Correct 113 ms 258520 KB Output is correct
11 Correct 110 ms 258608 KB Output is correct
12 Correct 125 ms 258664 KB Output is correct
13 Correct 111 ms 258592 KB Output is correct
14 Correct 109 ms 258500 KB Output is correct
15 Correct 119 ms 258612 KB Output is correct
16 Correct 111 ms 258564 KB Output is correct
17 Correct 125 ms 258600 KB Output is correct
18 Correct 113 ms 258552 KB Output is correct
19 Runtime error 309 ms 262152 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 260280 KB Output is correct
2 Correct 463 ms 260044 KB Output is correct
3 Correct 501 ms 260164 KB Output is correct
4 Correct 482 ms 260188 KB Output is correct
5 Correct 324 ms 260152 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 259000 KB Output is correct
2 Correct 182 ms 258988 KB Output is correct
3 Correct 180 ms 258964 KB Output is correct
4 Correct 164 ms 258996 KB Output is correct
5 Correct 111 ms 258496 KB Output is correct
6 Correct 162 ms 258996 KB Output is correct
7 Correct 168 ms 258992 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 730 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 258500 KB Output is correct
2 Correct 111 ms 258612 KB Output is correct
3 Correct 112 ms 258588 KB Output is correct
4 Correct 118 ms 258492 KB Output is correct
5 Correct 116 ms 258500 KB Output is correct
6 Correct 114 ms 258556 KB Output is correct
7 Correct 110 ms 258568 KB Output is correct
8 Correct 110 ms 258568 KB Output is correct
9 Correct 109 ms 258576 KB Output is correct
10 Correct 113 ms 258520 KB Output is correct
11 Correct 110 ms 258608 KB Output is correct
12 Correct 125 ms 258664 KB Output is correct
13 Correct 111 ms 258592 KB Output is correct
14 Correct 109 ms 258500 KB Output is correct
15 Correct 119 ms 258612 KB Output is correct
16 Correct 111 ms 258564 KB Output is correct
17 Correct 125 ms 258600 KB Output is correct
18 Correct 113 ms 258552 KB Output is correct
19 Runtime error 309 ms 262152 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -