oj.uz

Submission #1063719

# Submission time Handle Problem Language Result Execution time Memory
1063719 2024-08-18T00:11:41 Z sssamui Global Warming (CEOI18_glo) C++17
17 / 100
 33 ms 4816 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, x;
	cin >> n >> x;
	vector<int> pfxlissz(n);
	vector<int> lis(0);

	vector<int> t(n);
	for (int i = 0; i < n; i++) cin >> t[i];
	for (int i = 0; i < n; i++)
	{
		pfxlissz[i] = lis.size();
		if (lis.empty() || (lis.back() < x + t[i])) pfxlissz[i]++;
		if (lis.empty() || (lis.back() < t[i])) lis.push_back(t[i]);
		int l = lower_bound(lis.begin(), lis.end(), t[i]) - lis.begin();
		lis[l] = t[i];
	}

	vector<int> sfxldssz(n);
	lis.clear();
	for (int i = n - 1; i > -1; i--)
	{
		if (lis.empty() || (lis.back() + t[i] < 0)) lis.push_back(-t[i]);
		sfxldssz[i] = lower_bound(lis.begin(), lis.end(), -t[i]) - lis.begin();
		lis[sfxldssz[i]] = -t[i];
	}

	int ans = sfxldssz[0] + 1;
	for (int i = 1; i < n; i++) ans = fmax(ans, pfxlissz[i] + sfxldssz[i]);
	cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2396 KB Output is correct
2 Correct 17 ms 2392 KB Output is correct
3 Correct 33 ms 4736 KB Output is correct
4 Correct 18 ms 4412 KB Output is correct
5 Correct 9 ms 2528 KB Output is correct
6 Correct 17 ms 4372 KB Output is correct
7 Correct 21 ms 4816 KB Output is correct
8 Correct 14 ms 2396 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -