Submission #961192

#	Time	Username	Problem	Language	Result	Execution time	Memory
961192		Syrius	Global Warming (CEOI18_glo)	C++14	0 / 100	825 ms	84492 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)

const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;

int prelis[mxn] , suflis[mxn] , a[mxn] , ed[mxn];
int n , x;

void find1(int id) {
	int l = 0 , r = id-1;
	while (l != r) {
		int m = (l + r) / 2;
		if (ed[m+1] >= a[id]) r = m;
		else l = m+1;
	}
	prelis[id] = r + 1;
	ed[r+1] = min(a[id] , ed[r+1]);
}

void find2(int id) {
	int l = 0 , r = n - id;
	while (l != r) {
		int m = (l + r) / 2;
		if (ed[m+1] <= a[id]) r = m;
		else l = m + 1;
	}
	suflis[id] = r + 1;
	ed[r+1] = max(a[id] , ed[r+1]);
}

struct node {
	int tl , tm , tr , val;
	node *left , *right;

	node (int l , int r) {
		tl = l , tr = r , tm = (l + r) / 2;
		val = -inf;
		left = right = NULL;
	}

	void make() {
		if (left == NULL) left = new node(tl , tm);
		if (right == NULL) right = new node(tm+1 , tr);
	}

	void update(int p , int v) {
		if (tl == tr) {
			val = v;
			return;
		}
		make();
		if (p <= tm) left -> update(p , v);
		else right -> update(p , v);
		val = max(left -> val , right -> val);
	}

	int query(int r) {
		if (tl == tr) return val;
		make();
		if (r <= tm) return left -> query(r);
		return max(left -> val , right -> query(r));
	}
};

map < int , int > mp;
int cntr;
void compress() {
	set < int > comp;
	for (int i = 1; i <= n; i++) {
		comp.insert(a[i]);
		comp.insert(a[i] + x - 1);
	}
	for (int i : comp) {
		mp[i] = ++cntr;
	}
}

signed main() {

	cin >> n >> x;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	ed[0] = 0;
	for (int i = 1; i <= n; i++) ed[i] = inf;

	ed[1] = a[1] , prelis[1] = 1;
	for (int i = 2; i <= n; i++) find1(i);
	for (int i = 1; i <= n; i++) ed[i] = -inf;

	ed[0] = inf;
	ed[1] = a[n] , suflis[n] = 1;
	for (int i = n-1; i >= 1; i--) find2(i);

	compress();
	node *root = new node(0 , cntr);
	int ans = prelis[n];
	for (int i = 1; i < n; i++) {
		ans = max(ans , root -> query(mp[a[i+1]+x-1]) + suflis[i+1]);
		root -> update(mp[a[i]] , prelis[i]);
	}
	
	for (int i = 1; i <= n; i++) cout << prelis[i] << ' ';
	cout << '\n';
	for (int i = 1; i <= n; i++) cout << suflis[i] << ' ';
	cout << '\n';
	cout << ans << '\n';
	return 0;
}

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