Submission #827392

#	Time	Username	Problem	Language	Result	Execution time	Memory
827392		MadokaMagicaFan	Global Warming (CEOI18_glo)	C++14	27 / 100	219 ms	5356 KiB

glo

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25