Submission #246331

#	Time	Username	Problem	Language	Result	Execution time	Memory
246331		tonowak	Global Warming (CEOI18_glo)	C++14	100 / 100	244 ms	7544 KiB

glo

#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

struct Tree {
	int sz = 1;
	vector<int> tree;

	Tree(int n) {
		while(sz < n)
			sz *= 2;
		tree.resize(2 * sz);
	}

	void set(int v, int val) {
		tree[v += sz] = val;
		while(v /= 2)
			tree[v] = max(tree[2 * v], tree[2 * v + 1]);
	}

	int get_max(int l, int r) {
		if(l > r)
			return 0;
		int ret = max(tree[l += sz], tree[r += sz]);
		while(l / 2 != r / 2) {
			if(~l & 1)
				ret = max(ret, tree[l + 1]);
			if(r & 1)
				ret = max(ret, tree[r - 1]);
			l /= 2;
			r /= 2;
		}
		return ret;
	}
};

vector<int> sorted_values;

int get_id(int x) {
	return int(lower_bound(sorted_values.begin(), sorted_values.end(), x) - sorted_values.begin());
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, x;
	cin >> n >> x;
	vector<int> t(n);
	for(int &ti : t)
		cin >> ti;
	debug(n, x, t);

	sorted_values = t;
	sort(sorted_values.begin(), sorted_values.end());
	sorted_values.erase(unique(sorted_values.begin(), sorted_values.end()), sorted_values.end());
	debug(sorted_values);

	vector<int> answer_left(n), answer_right(n);
	Tree tree(size(sorted_values));
	for(int i = n - 1; i >= 0; --i) {
		int new_val = get_id(t[i]);
		answer_right[i] = tree.get_max(new_val + 1, size(sorted_values) - 1) + 1;
		tree.set(new_val, answer_right[i]);
	}

	fill(tree.tree.begin(), tree.tree.end(), 0);
	REP(i, n) {
		int new_val = get_id(t[i]);
		// int lowest = int(prev(lower_bound(sorted_values.begin(), sorted_values.end(), t[i] + x)) - sorted_values.begin());
		int lowest = get_id(t[i] + x) - 1;
		debug(i, new_val, lowest);
		answer_left[i] = tree.get_max(0, lowest);
		tree.set(new_val, tree.get_max(0, new_val - 1) + 1);
	}
	debug(answer_left, answer_right);
	int answer = 0;
	REP(i, n)
		answer = max(answer, answer_left[i] + answer_right[i]);
	cout << answer << '\n';
}

• 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