Submission #943812

#	Time	Username	Problem	Language	Result	Execution time	Memory
943812		pcc	Global Warming (CEOI18_glo)	C++17	100 / 100	50 ms	4308 KiB

glo

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
int N,X;
int arr[mxn];
int dp[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>X;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	vector<int> v;
	for(int i = N;i>=1;i--){
		auto pos = lower_bound(v.begin(),v.end(),-arr[i])-v.begin();
		dp[i] = pos+1;
		if(pos == v.size())v.push_back(-arr[i]);
		else v[pos] = -arr[i];
	}
	v.clear();
	int ans = *max_element(dp+1,dp+N+1);
	for(int i = 1;i+1<=N;i++){
		auto pos = lower_bound(v.begin(),v.end(),arr[i])-v.begin();
		if(pos == v.size())v.push_back(arr[i]);
		else v[pos] = arr[i];
		int tans = dp[i+1];
		tans += lower_bound(v.begin(),v.end(),arr[i+1]+X)-v.begin();
		ans = max(ans,tans);
	}
	cout<<ans<<'\n';
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:25:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   if(pos == v.size())v.push_back(-arr[i]);
      |      ~~~~^~~~~~~~~~~
glo.cpp:32:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   if(pos == v.size())v.push_back(arr[i]);
      |      ~~~~^~~~~~~~~~~

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