Submission #961072

#	Time	Username	Problem	Language	Result	Execution time	Memory
961072		BF001	Global Warming (CEOI18_glo)	C++17	100 / 100	53 ms	4700 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#define N 200005

int n, a[N], cnt, lf[N], val[N], x;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
   	cin >> n >> x;
   	for (int i = 1; i <= n; i++) cin >> a[i];

   	for (int i = 1; i <= n; i++){
   		int l = 1, r = cnt, rt = 0;
   		while (l <= r){
   			int mid = (l + r) >> 1;
   			if (val[mid] < a[i]){
   				rt = mid;
   				l = mid + 1;
   			}
   			else r = mid - 1;
   		}
   		if (rt == cnt) cnt++;
   		val[rt + 1] = a[i];
   		lf[i] = rt + 1;
   	}

   	cnt = 0;
   	int res = 0;
   	for (int i = n; i >= 1; i--){
   		int l = 1, r = cnt, rt = 0;
   		while (l <= r){
   			int mid = (l + r) >> 1;
   			if (a[i] - x < val[mid]){
   				rt = mid;
   				l = mid + 1;
   			}
   			else r = mid - 1;
   		}
   		res = max(res, lf[i] + rt);
   		l = 1, r = cnt, rt = 0;
   		while (l <= r){
   			int mid = (l + r) >> 1;
   			if (a[i] < val[mid]){
   				l = mid + 1;
   				rt = mid;
   			}
   			else r = mid - 1;
   		}
   		if (rt == cnt) cnt++;
   		val[rt + 1] = a[i];
   	}

   	cout << res;

    return 0;
}     

• 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