Submission #1331534

#TimeUsernameProblemLanguageResultExecution timeMemory
1331534tkm_algorithmsGlobal Warming (CEOI18_glo)C++20
37 / 100
374 ms31168 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;

struct segtree {
	vector<int> tree;
	int size;
	
	void init(int n) {
		size = 1;
		while (size<n)size <<= 1;
		tree.assign(2*size-1, 0);
	}
	
	void upd(int i, int v, int x, int lx, int rx) {
		if (rx-lx==1) {
			tree[x] = max(tree[x], v);
			return;
		}
		
		int mid = lx+rx>>1;
		if(i<mid)upd(i,v,2*x+1,lx,mid);
		else upd(i,v,2*x+2,mid,rx);
		tree[x] = max(tree[2*x+1], tree[2*x+2]);
	}
	
	void upd(int i, int v) {
		upd(i, v, 0, 0, size);
	}
	
	int get(int l,int r,int x, int lx, int rx) {
		if (rx <= l || r <= lx)return 0;
		if (l <= lx && rx <= r)return tree[x];
		int mid = lx+rx>>1;
		return max(get(l, r, 2*x+1,lx,mid),
				   get(l, r, 2*x+2,mid,rx));
	}
	
	int get(int l, int r) {
		return get(l,r,0,0,size);
	}
};

int n, x;
vector<int> c(vector<int> a) {
	vector<int> b = a;
	sort(all(a)); int t = 1;
	map<int, int> mp;
	rep(i, 0, n)
		if (i == 0 || a[i] != a[i-1])mp[a[i]] = t++;
	for (auto &i: b)i = mp[i];
	return b;
}

void solve() {
	cin >> n >> x;
	vector<int> a(n);
	for (auto &i: a)cin >> i;
	
	vector<int> A = a, b;
	set<int> setik;
	rep(i, 0, n)setik.insert(a[i]);
	for(auto i: setik)b.push_back(i);
	a = c(a);
	
	vector<int> p(n), s(n);
	
	segtree pt, st, ls;
	pt.init(n+3), st.init(n+3);
	ls.init(n+3);
	
	rep(i, 0, n) {
		p[i] = pt.get(0, a[i])+1;
		pt.upd(a[i], p[i]);
	}
	
	//rep(i, 1, n)p[i] = max(p[i-1], p[i]);
	
	//rep(i, 0, n)
		//cout << p[i] << " ";
	//cout << nl;
	// 8 9 10 2 3 10
	
	int res = p[n-1];
	for (int i = n-1; i >= 1; --i) {
		s[i] = st.get(a[i]+1, n+2)+1;
		st.upd(a[i], s[i]);
	}
	
	//cout << "b: ";for (auto i: b)cout << i << " ";
	//cout << nl;
	
	//cout << "p: ";for (auto i: p)cout << i << " ";
	//cout << nl;
	
	rep(i, 0, n) {
		int y = A[i];
		int lb = lower_bound(all(b), y) - b.begin();
		int ub = lower_bound(all(b), y+x)-b.begin();
		ub--;
		if (lb > ub) {
			ls.upd(lb+1, p[i]);
			continue;
		}
		//if (i == 5)cout << lb << " " << ub << " " << ls.get(6, 7) << " " << s[i] << nl;
		res = max(res, s[i]+ls.get(lb+1, ub+2));
		ls.upd(lb+1, p[i]);
		//if (y == 10)cout << p[i] << nl;
	}
	
	cout << res << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...