Submission #383234

#	Time	Username	Problem	Language	Result	Execution time	Memory
383234		maximath_1	Global Warming (CEOI18_glo)	C++11	100 / 100	70 ms	4684 KiB

glo

#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 10005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
 
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}

int LIS(vector<int> v){
	int sz = v.size();

	vector<int> dp;
	for(int i = 0; i < sz; i ++){
		auto it = lower_bound(dp.begin(), dp.end(), v[i]);
		if(it == dp.end()) dp.push_back(v[i]);
		else dp[it - dp.begin()] = v[i];
	}

	return dp.size();
}

int n, x;
vector<int> v;

int main(){
	cin(n); cin(x);
	v.resize(n);
	for(int i = 0; i < n; i ++)
		cin(v[i]);

	int ans = LIS(v);

	vector<int> suff(n), dp; dp.assign(n, 0);
	for(int i = n - 1; i >= 0; i --){
		int it = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin() - 1;
		dp[it] = v[i];
		suff[i] = n - it;
	}

	dp.clear();
	for(int i = 0; i < n; i ++){
		int j = upper_bound(dp.begin(), dp.end(), v[i] + x - 1) - dp.begin();
		ans = max(ans, j + suff[i]);
		auto it = lower_bound(dp.begin(), dp.end(), v[i]);
		if(it == dp.end()) dp.push_back(v[i]);
		else dp[it - dp.begin()] = v[i];
	}

	printf("%d\n", ans);

	return 0;
}

• 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