Submission #963179

#	Time	Username	Problem	Language	Result	Execution time	Memory
963179		noobcodur	Global Warming (CEOI18_glo)	C++14	100 / 100	48 ms	9440 KiB

glo

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

using ld = long double;

#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;

void setIO(string name){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if(!name.empty()){
		freopen((name + ".in").c_str(),"r",stdin);
		freopen((name + ".out").c_str(),"w",stdout);
	}
}

int l[maxN],r[maxN];

signed main(){
	setIO("");
	int n,x; cin >> n >> x;
	vi a(n),b(n);

	forn(i,n){
		cin >> a[i];
		b[i] = -a[i];
	}

	vi dp;

	forn(i,n){
		if(dp.empty() || dp.back() < a[i]){
			dp.pb(a[i]);
			l[i] = dp.size();
			continue;
		}

		int j = lower_bound(all(dp),a[i]) - dp.begin();
		dp[j] = a[i];
		l[i] = j+1;
	}

	dp.clear();

	for(int i = n-1; i >= 0; --i){
		int j = lower_bound(all(dp),b[i]+x) - dp.begin();
		r[i] = j+1;	

		j = lower_bound(all(dp),b[i]) - dp.begin();

		if(j == dp.size()){
			dp.pb(b[i]);
		}

		else{
			dp[j] = b[i];
		}
	}

	int res = 0;

	forn(i,n){
		res = max(res,l[i]+r[i]-1);
	}

	cout << res << endl;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:63:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if(j == dp.size()){
      |      ~~^~~~~~~~~~~~
glo.cpp: In function 'void setIO(std::string)':
glo.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   freopen((name + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen((name + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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