Submission #725227

#	Time	Username	Problem	Language	Result	Execution time	Memory
725227		pavement	Global Warming (CEOI18_glo)	C++17	100 / 100	413 ms	19592 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int n, x, ans, t[200005], pf[200005], sf[200005], ft[800005];
vector<int> disc;

int ls(int x) { return x & -x; }

void upd(int p, int v) {
	for (; p <= (int)disc.size(); p += ls(p)) ft[p] = max(ft[p], v);
}

int qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r = max(r, ft[p]);
	return r;
}

int f(int x) {
	return lower_bound(disc.begin(), disc.end(), x) - disc.begin() + 1;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
		disc.pb(t[i]);
		disc.pb(t[i] - 1);
		disc.pb(t[i] + 1);
		disc.pb(t[i] + x - 1);
	}
	sort(disc.begin(), disc.end());
	disc.erase(unique(disc.begin(), disc.end()), disc.end());
	for (int i = 1; i <= n; i++) {
		pf[i] = qry(f(t[i] - 1)) + 1;
		upd(f(t[i]), pf[i]);
	}
	for (int i = 1; i <= (int)disc.size(); i++) {
		ft[i] = 0;
	}
	for (int i = n; i >= 1; i--) {
		sf[i] = qry(disc.size() - f(t[i] + 1) + 1) + 1;
		upd(disc.size() - f(t[i]) + 1, sf[i]);
	}
	for (int i = 1; i <= (int)disc.size(); i++) {
		ft[i] = 0;
	}	
	for (int i = 1; i <= n; i++) {
		ans = max(ans, qry(f(t[i] + x - 1)) + sf[i]);
		upd(f(t[i]), pf[i]);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

glo.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main() {
      | ^~~~

• 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