Submission #641102

#	Time	Username	Problem	Language	Result	Execution time	Memory
641102		ymm	Global Warming (CEOI18_glo)	C++17	100 / 100	1884 ms	4708 KiB

glo

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
int a[N];
int n, d;

int s1[N], s2[N];

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(int l, int r, int x)
{
	Loop (i,l,r)
		s2[i] = x;
}

int solve()
{
	Loop (i,0,N)
		s1[i] = s2[i] = INT_MAX;
	Loop (i,0,n) {
		int l = lower_bound(s2, s2 + N, a[i]) - s2;
		int r = lower_bound(s1, s1 + N, a[i] + d) - s1;
		s2[l] = a[i];
		up(l+1, r+1, a[i]);

		int j = lower_bound(s1, s1 + N, a[i]) - s1;
		s1[j] = a[i];

		//for (int x : s1) { if (x == INT_MAX) { break; } cout << x << ' '; } cout << "!\n";
		//for (int x : s2) { if (x == INT_MAX) { break; } cout << x << ' '; } cout << "!\n";
		//cout << "--\n\n";
	}
	return lower_bound(s2, s2+N, INT_MAX) - s2;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> d;
	Loop (i,0,n)
		cin >> a[i];
	int ans = solve();
	Loop (i,0,n) a[i] = -a[i];
	reverse(a, a+n);
	ans = max(ans, solve());
	cout << ans << '\n';
}

• 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