Submission #641096

#	Time	Username	Problem	Language	Result	Execution time	Memory
641096		ymm	Global Warming (CEOI18_glo)	C++17	58 / 100	2076 ms	3712 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 solve()
{
	vector<int> s1, s2;
	Loop (i,0,n) {
		int l = lower_bound(s2.begin(), s2.end(), a[i]) - s2.begin();
		if (l == s2.size()) s2.push_back(INT_MAX);
		assert(l < s2.size());

		int r = lower_bound(s1.begin(), s1.end(), a[i] + d) - s1.begin();
		if (r == s2.size()) s2.push_back(INT_MAX);
		assert(r < s2.size());

		if (l > r) swap(l, r);
		Loop (j,l,r+1) s2[j] = min(a[i], s2[j]);

		int j = lower_bound(s1.begin(), s1.end(), a[i]) - s1.begin();
		if (j == s1.size()) s1.push_back(INT_MAX);
		assert(j < s1.size());
		s1[j] = min(a[i], s1[j]);

		//for (int x : s1) { cout << x << ' '; } cout << "!\n";
		//for (int x : s2) { cout << x << ' '; } cout << "!\n";
		//cout << "--\n\n";
	}
	return s2.size();
}

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

Compilation message (stderr)

glo.cpp: In function 'int solve()':
glo.cpp:18:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   if (l == s2.size()) s2.push_back(INT_MAX);
      |       ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from glo.cpp:1:
glo.cpp:19:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   assert(l < s2.size());
      |          ~~^~~~~~~~~~~
glo.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if (r == s2.size()) s2.push_back(INT_MAX);
      |       ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from glo.cpp:1:
glo.cpp:23:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   assert(r < s2.size());
      |          ~~^~~~~~~~~~~
glo.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if (j == s1.size()) s1.push_back(INT_MAX);
      |       ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from glo.cpp:1:
glo.cpp:30:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   assert(j < s1.size());
      |          ~~^~~~~~~~~~~

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