Submission #486975

#	Time	Username	Problem	Language	Result	Execution time	Memory
486975		Duy_e	Global Warming (CEOI18_glo)	C++14	0 / 100	3 ms	1868 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<long long, long long>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long oo = 1e18;
const long long N = 2e5 + 5;

ll n, a[N], x, lis[N], lds[N];
vector <ll> dp(N, 3e9);

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
	#endif
	
	cin >> n >> x;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];

	for (int i = n; i >= 1; i --){
		lds[i] = lower_bound(dp.begin(), dp.end(), - a[i]) - dp.begin() + 1;
		dp[lds[i] - 1] = -a[i];
	}

	dp.assign(N, 3e9);
	ll ans = 0;
	for (int i = 1; i <= n; i ++){
		lis[i] = lower_bound(dp.begin(), dp.end(), a[i] - x) - dp.begin() + 1;
		

		ans = max(ans, lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin() + lds[i]);

		dp[lis[i] - 1] = a[i] - x;
		// cout << lis[i] << ' ';
	}

	cout << ans;

	return 0;
}	
/**  /\_/\
    (= ._.)
    / >0  \>1 
  ________________________
 / Brainstorming section /
/=======================/
---
===
To be frank I did not quite get your way of thinking, but let me put it my way. 
Let's say we modify some subsegment [i, j] (we do not say anything about whether 
some points in it will belong to our final LIS or whatever). 
Let's say we move it down by y. 
We can note that we in fact can move down [1, i-1] segment as well, 
because moving down some prefix never decreases LIS. 
So it turns out that we can in fact restrict to moving prefix [1, j] down under the assumption
that we moved our subsegment down. Moreover we can move it down as far as we can and 
it will not worsen our answer, so we can restrict our move here to x what almost proves my claim.
There is second case to consider of subsegment being moved up, 
in which case we see that we can move suffix [i, n] by x up, but that is 
the same as moving prefix [1, i-1] down by x.
===
**/
// Before submit: spot the visible bug by reading the code.

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
glo.cpp:19:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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