Submission #948539

#	Time	Username	Problem	Language	Result	Execution time	Memory
948539		dio_2	Global Warming (CEOI18_glo)	C++17	28 / 100	2083 ms	27376 KiB

glo

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

struct MaxSegree{
	MaxSegree () {}
	MaxSegree (int N){
		build(N);
	}
	int base;
	const int neutral = -(int)1e9;
	vector<int> maxy;
	
	void build(int N){
		base = 1;
		while(base <= N) base *= 2;
		maxy.assign(2 * base, neutral);
	}
	
	void pull(int node){
		maxy[node] = max(maxy[2 * node], maxy[2 * node + 1]);
	}
	
	void update(int node, int lx, int rx, int pos, int val){
		if(lx == rx){
			assert(lx == pos);
			maxy[node] = val;
			return ;
		}
		int mid = (lx + rx) / 2;
		if(pos <= mid){
			update(2 * node, lx, mid, pos, val);
		} else {
			update(2 * node + 1, mid + 1, rx, pos, val);
		}
		pull(node);
	}
	
	int Max(int node, int lx, int rx, int l, int r){
		if(lx > r || rx < l) return neutral;
		if(l <= lx && rx <= r) return maxy[node];
		int mid = (lx + rx) / 2;
		return max(Max(2 * node, lx, mid, l, r), Max(2 * node + 1, mid + 1, rx, l, r));
	}
	
	void update(int pos, int val){
		update(1, 1, base, pos, val);
	}
	
	int Max(int l, int r){
		return Max(1, 1, base, l, r);
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, x;
	cin >> n >> x;
	
	vector<int> t(n);
	set<int> s;
	map<int, int> comp;
	for(int &y : t){
		cin >> y;
		s.insert(y);
	}
	
	// compress for RMQ.
	int cnt = 1;
	for(int y : s){
		comp[y] = cnt++;
	}
	
	MaxSegree LIS(n), LDS(n);
	vector<int> dp(n, 1), dp2(n, 1);
	for(int i = 0;i < n;i++){
		if(comp[t[i]] - 1 >= 1){
			dp[i] = max(dp[i], LIS.Max(1, comp[t[i]] - 1) + 1);
		}
		LIS.update(comp[t[i]], dp[i]);
	}
	
	int answer = 0;
	for(int i = n - 1;i >= 0;i--){
		if(comp[t[i]] + 1 <= n){
			dp2[i] = max(dp2[i], LDS.Max(comp[t[i]] + 1, n) + 1);
		}
		LDS.update(comp[t[i]], dp2[i]);
		answer = max(answer, dp2[i]);
		if(i - 1 >= 0){
			int prev_val = t[i - 1] - x;
			// find first strictly <
			for(int j = i;j < n;j++){
				if(prev_val < t[j]){
					answer = max(answer, dp[i - 1] + dp2[j]);
				}
			}
		}
	}
	

	cout << answer << '\n';
	
	return 0;
}

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