Submission #940032

#	Time	Username	Problem	Language	Result	Execution time	Memory
940032		vjudge1	Global Warming (CEOI18_glo)	C++17	100 / 100	80 ms	10984 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int INF = 3e9 + 7;
int LIS(vector<int> a){
	 
	set<int> dp;
	for(int i = 0;i < (int)a.size(); i++){		
		int x = a[i];
		if(dp.lower_bound(x) != dp.end()) dp.erase(dp.lower_bound(x));
		dp.insert(x);
	}
	return (int)dp.size();
} 

main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
	int x; cin >> x;
	vector<int> a(n), b(n);
	for(int i = 0;i < n; i++){
		cin >> a[i];
		b[i] = -a[i];
	}
	vector<int> suf(n+1, INF), suf_ans(n, 0);
	suf[0] = -INF;
	for(int i = n-1; i >= 0; i--){
		int j = upper_bound(all(suf), b[i]) - suf.begin();
		if(suf[j-1] < b[i] && b[i] < suf[j]){
			suf_ans[i] = max(suf_ans[i], j);
			suf[j] = b[i];
		}
	}
	
	int ans = LIS(a);
	vector<int> dp(n + 1, INF), pref_ans(n, 0);
	dp[0] = -INF;
	for(int i = 0;i < n; i++){
		int j = int(upper_bound(dp.begin(), dp.end(), a[i])  - dp.begin());
		if(dp[j - 1] < a[i] and a[i] < dp[j]){
			dp[j] = a[i];
			pref_ans[i] = max(pref_ans[i], j);
		} 
		if(i + 1 < n){
			int d = a[i + 1] + x;
			int it = upper_bound(all(dp), d) - dp.begin();
			if(dp[it-1] < d){
				ans = max(ans, suf_ans[i+1] + it-1);
			}
		}
		
	}
	
	
	
	cout << ans;
    return 0;
}

Compilation message (stderr)

glo.cpp:6:21: warning: overflow in conversion from 'double' to 'int' changes value from '3.000000007e+9' to '2147483647' [-Woverflow]
    6 | const int INF = 3e9 + 7;
      |                 ~~~~^~~
glo.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main(){
      | ^~~~

• 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