제출 #1278718

#제출 시각아이디문제언어결과실행 시간메모리
1278718IBoryGlobal Warming (CEOI18_glo)C++20
100 / 100
216 ms9328 KiB
#include <bits/stdc++.h>
using namespace std;

const int SZ = 1 << 19;
int S[SZ];

struct Seg {
	int T[SZ << 1];
	void Update(int i, int v) {
		i += SZ - 1;
		T[i] = max(T[i], v);
		while (i >>= 1) T[i] = max(T[i * 2], T[i * 2 + 1]);
	}
	int Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
		if (L > R || R < sL || sR < L) return 0;
		if (L <= sL && sR <= R) return T[n];
		int mid = (sL + sR) >> 1;
		return max(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, n * 2 + 1));
	}
} T1, T2;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, X;
	cin >> N >> X;
	vector<int> U;
	for (int i = 1; i <= N; ++i) {
		cin >> S[i];
		U.push_back(S[i]); U.push_back(S[i] + X);
	}
	U.push_back(-1);
	sort(U.begin(), U.end());
	U.erase(unique(U.begin(), U.end()), U.end());

	for (int i = 1; i <= N; ++i) {
		int p = lower_bound(U.begin(), U.end(), S[i]) - U.begin();
		int q = lower_bound(U.begin(), U.end(), S[i] + X) - U.begin();
		int a = T1.Query(1, p - 1) + 1;
		int b = max(T1.Query(1, q - 1), T2.Query(1, q - 1)) + 1;
		T1.Update(p, a);
		T2.Update(q, b);
	}

	int ans = T2.Query(1, SZ);
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...