oj.uz

Submission #961162

# Submission time Handle Problem Language Result Execution time Memory
961162 2024-04-11T15:25:14 Z Syrius Global Warming (CEOI18_glo) C++14
0 / 100
 1089 ms 61152 KB 
#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] , ed[mxn] , a[mxn];
int n , x;

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

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

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;
	}
}

int 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]+x-1]) + suflis[i+1]);
		root -> update(mp[a[i]] , prelis[i]);
	}

	cout << ans << '\n';
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 750 ms 60980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 17232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 31792 KB Output is correct
2 Correct 446 ms 31760 KB Output is correct
3 Correct 1089 ms 61152 KB Output is correct
4 Incorrect 190 ms 32308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -