Submission #653342

#	Time	Username	Problem	Language	Result	Execution time	Memory
653342		aebov	Global Warming (CEOI18_glo)	C++17	48 / 100	746 ms	41036 KiB

glo

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstring>
#include<utility>
#define ll long long
#define ln (e-s+1)
#define md ((e+s)/2)
#define dm ((e+s)/2+1)
#define lc (id*2)
#define rc (id*2 + 1)
#define pb push_back
#define F first
#define S second
using namespace std;

const int N = (int)1e5 + 500, N2 = N << 1;
int n , a[N], m, x;
int seg[N2 << 2];
vector<int> vc;
int ans = 0, dp[N], dp2[N], dp3[N];
map<int, vector<int>> pos;
set<int> st, st2;

void upd(int k, int p,int id = 1,int s = 1,int e = n){
	if( k < s || k > e)return;
	if(ln == 1){
		seg[id] = p;
		return;
	}
	if( k <= md)upd(k, p, lc, s, md), seg[id] = max(seg[lc], seg[rc]);
	else upd(k, p, rc, dm, e), seg[id] = max(seg[lc], seg[rc]);
}
int get(int l, int r,int id = 1,int s = 1,int e = n){
	if( r < s || l > e)return 0;
	if( l <= s && e <= r)return seg[id];
	return max(get(l, r, lc, s, md), get(l, r, rc, dm, e));
}

int main(){

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> x;
	for(int i = 1; i <= n; i ++) cin >> a[i] , st.insert(a[i]), st2.insert(- a[i]);
	for(int i = 1; i <= n; i ++) pos[a[i]].pb(i);
	
	for(auto i : st){
		for(auto ind : pos[i]){
			dp[ind] = get(1, ind - 1) + 1;
	//		cout << ind << " " << a[ind] << " " << get(1, ind - 1) << endl;
		}
		for(auto ind : pos[i]){
			upd(ind, dp[ind]);
	//		cout << "##" << ind << " " << dp[ind] << endl;
		}
	}for(int i = 1; i <= n; i ++) ans = max(ans, dp[i]);
	
	fill( seg, seg + (n << 2) + 100, 0);
	set<pair<int,bool> > st3;
	for(int i = 1; i <= n; i ++)st3.insert({-a[i], 1}), st3.insert({-(a[i]- x), 0});
	for(auto  p : st3){
		int i = -p.F;
		if(p.S == 0){
			for(auto ind : pos[i + x]){
				ans = max(ans, dp[ind] + get(ind + 1, n));
			//	cout << ind << " " << a[ind]  << " : " << dp[ind] << " , " << get(ind + 1, n) << endl;
			}
			continue;
		}
		for(auto ind : pos[i]) dp2[ind] = get(ind + 1, n) + 1;
		for(auto ind : pos[i])  upd(ind, dp2[ind]);
	}
	
	st3.clear();
	fill(seg, seg + ( n << 2) + 100, 0);
	for(int i = 1; i <= n ;i ++)st3.insert({a[i], 1}), st3.insert({a[i] + x, 0});
	for(auto  p : st3){
		int i = p.F;
		if(p.S == 0){
			for(auto ind : pos[i + x]){
				ans = max(ans, dp2[ind] + get(1, ind - 1));
			}
			continue;
		}
		for(auto ind : pos[i]) dp3[ind] = get(1, ind - 1) + 1;
		for(auto ind : pos[i]) upd(ind, dp3[ind]);
	}
	cout << ans << endl;
	
}

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