Submission #1268203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268203		WH8	Global Warming (CEOI18_glo)	C++20	0 / 100	150 ms	22204 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'

const int maxn=500005;
int fw[2][500005];

int qry(int st, int x){
	int ret=0;
	while(x){
		ret=max(ret, fw[st][x]);
		x-=(x&(-x));
	}
	return ret;
}
void upd(int st, int x, int v){
	while(x <= maxn){
		fw[st][x]=max(fw[st][x],v);
		x+=(x&(-x));
	}
}

signed main(){
	int n,d;cin>>n>>d;
	vector<pair<int,int>> v(n);
	vector<int> t(n), disc;
	
	for(int i=0;i<n;i++){
		cin>>t[i];
		disc.pb(t[i]);
		disc.pb(t[i]+d);
	}
	sort(disc.begin(),disc.end());
	disc.erase(unique(disc.begin(),disc.end()),disc.end());
	for(int i=0;i<n;i++){
		v[i].f=lower_bound(disc.begin(),disc.end(),t[i])-disc.begin()+1;
		v[i].s=lower_bound(disc.begin(),disc.end(),t[i]+d)-disc.begin()+1;
		//~ cout<<v[i].f<<" "<<v[i].s<<endl;
	}
	vector<vector<int>> dp(n, vector<int>(2, 0));
	int ans=0;
	for(int i=0;i<n;i++){
		dp[i][0]=qry(0,v[i].f-1)+1;
		dp[i][1]=max(qry(0, v[i].s-1), qry(1, v[i].f))+1;
		upd(0, v[i].f, dp[i][0]);
		upd(1, v[i].f, dp[i][1]);
		ans=max(dp[i][0],dp[i][1]);
		//~ printf("0 %lld 1 %lld\n",dp[i][0],dp[i][1]);
	}
	cout<<ans;
	
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25