Submission #1311944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311944		kevins	Global Warming (CEOI18_glo)	C++20	5 / 100	142 ms	8244 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct fen{
	vector <ll> bit;
	ll n;
	fen(ll _n){
		n = _n;
		bit.resize(n+1, 1);
	}
	void upd(ll f, ll v){
		while (f <= n){
			bit[f] = max(bit[f], v);
			f += (f&(-f));
		}
	}

	ll qry(ll f){
		ll rm = 0;
		while (f > 0){
			rm = max(rm, bit[f]);
			f -= (f&(-f));
		}
		return rm;
	}
};
int main(){
	//we can decrease a prefix of the array by d or increase a suffix by d optimimally
	//we will increase a suffix by d
	//let dp[i][j] denote maximum lis from 1 to i, with j being a boolean flag of whether we have started increasing or not
	//dp[i][1] = max( max((dp[k][1] + 1), where 1 <= k < i and a[k] < a[i]), max((dp[k][0] + 1), where 1 <= k < i and a[k] < a[i]+d) )
	//dp[i][0] = max(dp[k][0] + 1)

	ll n, x;
	cin >> n >> x;

	ll a[n+1];
	vector <ll> dis;
	for (ll i = 1; i <= n; ++i){
		cin >> a[i];
		dis.push_back(a[i]);
		dis.push_back(a[i] + x);
	}

	sort(dis.begin(), dis.end());
	dis.erase(unique(dis.begin(), dis.end()), dis.end());

	auto compress = [&](ll v){
		return lower_bound(dis.begin(), dis.end(), v) - dis.begin() + 1;
	};

	fen* fw0 = new fen(dis.size()+1); //bool flag = 0
	fen* fw1 = new fen(dis.size()+1); //bool flag = 1

	ll running = 0;

	for (ll i = 2; i <= n; ++i){
		ll disVal = compress(a[i]);
		ll dpOne1 = fw1->qry(disVal-1) + 1;
		ll dpOne2 = fw0->qry(compress(a[i] + x) - 1) + 1;
		ll dpZero = fw0->qry(disVal-1) + 1;

		fw1->upd(disVal, max(dpOne1, dpOne2));
		fw0->upd(disVal, dpZero);
		running = max(running, max(max(dpOne1, dpOne2), dpZero));
	}

	cout << running << "\n";
}

• Subtask 1: 5 / 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