제출 #1278718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278718		IBory	Global Warming (CEOI18_glo)	C++20	100 / 100	216 ms	9328 KiB

glo

#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;
}

• 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