oj.uz

Submission #94453

# Submission time Handle Problem Language Result Execution time Memory
94453 2019-01-18T16:47:14 Z Noam527 Global Warming (CEOI18_glo) C++17
0 / 100
 77 ms 6380 KB 
#include <bits/stdc++.h>
#include <unordered_set>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' '  && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

int n, x;
vector<int> a;

vector<int> dp[2];
int L[2] = {};
vector<pair<int, int>> rev;

int upd(int ind, int val) {
	int lo, hi, mid;
	if (ind == 0) {
		lo = 0, hi = L[0] + 1;
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (val < dp[0][mid]) hi = mid;
			else lo = mid + 1;
		}
		rev.push_back({ lo, dp[0][lo] });
		dp[0][lo] = val;
		L[0] = max(L[0], lo);
	}
	else {
		lo = 0, hi = L[1] + 1;
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (val > dp[1][mid]) hi = mid;
			else lo = mid + 1;
		}
		dp[1][lo] = val;
		L[1] = max(L[1], lo);
	}
	return lo;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> x;
	a.resize(n);
	dp[0].resize(n + 1, 2 * inf), dp[1].resize(n + 1, -2 * inf);
	dp[0][0] = -2 * inf;
	dp[1][0] = 2 * inf;

	for (auto &i : a) cin >> i, upd(0, i);
	int ans = L[0];
	for (int i = n - 1, pos1, pos0; i >= 0; i--) {
		pos1 = upd(1, a[i]);
		pos0 = rev.back().first;
		dp[0][rev.back().first] = rev.back().second;
		if (rev.back().second == 2 * inf) L[0]--;
		rev.pop_back();

//		cout << "i " << i << '\n';
//		for (int j = 0; j <= L[0] + 1; j++) cout << dp[0][j] << " "; cout << '\n';
//		for (int j = 0; j <= L[1] + 1; j++) cout << dp[1][j] << " "; cout << '\n';

		int lo, hi, mid;
		lo = 0, hi = L[1];
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (dp[0][pos0] - x < dp[1][mid]) lo = mid;
			else hi = mid - 1;
		}
//		cout << "try 1: " << pos0 << " + " << lo << '\n';
		ans = max(ans, pos0 + lo);

		lo = 0, hi = L[0];
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (dp[1][pos1] + x > dp[0][mid]) lo = mid;
			else hi = mid - 1;
		}
//		cout << "try 2: " << pos1 << " + " << lo << '\n';
		ans = max(ans, pos1 + lo);
	}
	finish(ans);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 6256 KB Output is correct
2 Correct 77 ms 6256 KB Output is correct
3 Correct 76 ms 6376 KB Output is correct
4 Correct 76 ms 6380 KB Output is correct
5 Incorrect 51 ms 5872 KB Output isn't correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2068 KB Output is correct
2 Correct 19 ms 2040 KB Output is correct
3 Correct 20 ms 2040 KB Output is correct
4 Incorrect 13 ms 1784 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3512 KB Output is correct
2 Correct 28 ms 3572 KB Output is correct
3 Correct 58 ms 6256 KB Output is correct
4 Incorrect 50 ms 5876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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