제출 #827394

#제출 시각아이디문제언어결과실행 시간메모리
827394MadokaMagicaFanGlobal Warming (CEOI18_glo)C++14
100 / 100
216 ms5380 KiB
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define pb push_back
#define sz(v) ((int)v.size())

const ll inf = 1e16;

vector<int> nm;

int bs(int x) {
	int l, r, m;
	l = 0;
	r = sz(nm);
	while (l < r) {
		m = (l+r)/2;
		if (nm[m] <= x)
			l = m+1;
		else
			r = m;
	}
	return l;
}

struct aib {
	int n;
	vector<int> f;

	aib(int _n) : n(_n)
	{
		f.assign(n, 0);
	}

	void upd(int x, int v) {
		f[x] = max(f[x], v);
		for (; x < n; x |= (x+1))
			f[x] = max(f[x], v);
	}

	int qry(int x) {
		int r = 0;
		for (; x >=0; x = (x&(x+1))-1)
			r = max(f[x], r);
		return r;
	}
};

int main() {
	int n, d;
	cin >> n >> d;
	
	vector<int> t(n);
	for (int i = 0; i < n; ++i)
		cin >> t[i];
	nm = t;
	sort(nm.begin(), nm.end());
	nm.erase(unique(nm.begin(), nm.end()), nm.end());

	aib z[2] {sz(nm)+5, sz(nm)+5};
	
	for (auto x : t) {
		z[1].upd(bs(x), 1 + z[1].qry(bs(x-1)));
		z[1].upd(bs(x), 1 + z[0].qry(bs(x + d-1)));
		z[0].upd(bs(x), 1 + z[0].qry(bs(x-1)));
	}

	cout << max(z[0].qry(sz(nm)+4), z[1].qry(sz(nm)+4)) << endl;;
}
#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...