Submission #385684

#	Time	Username	Problem	Language	Result	Execution time	Memory
385684		ritul_kr_singh	Global Warming (CEOI18_glo)	C++17	0 / 100	259 ms	17388 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl << '\n'
#define sp << ' ' <<

struct SegmentTree{
	vector<int> a; int sz = 1, ID = -1e18;
	SegmentTree(vector<int> &v){
		while(sz < (int)v.size()) sz += sz;
		a.resize(2*sz, ID);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx<(int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx+rx)/2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int val, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = val);
		int mx = (lx+rx)/2;
		if(i<mx) update(i, val, 2*x+1, lx, mx);
		else update(i, val, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int val){ update(i, val, 0, 0, sz); }
	int get(int l, int r, int x, int lx, int rx){
		if(r<=lx or rx<=l) return ID;
		if(l<=lx and rx<=r) return a[x];
		int mx = (lx+rx)/2;
		return max(get(l, r, 2*x+1, lx, mx), get(l, r, 2*x+2, mx, rx));
	}
	int get(int l, int r){ return get(l, r+1, 0, 0, sz); }
};

void lis(int n, vector<int> &a, vector<int> &res){
	vector<int> v = {a[0]};
	res[0] = 1;
	for(int i=1; i<n; ++i){
		if(v.back() < a[i]) v.push_back(a[i]), res[i] = v.size();
		else{
			auto f = lower_bound(v.begin(), v.end(), a[i]);
			res[i] = f - v.begin() + 1;
			*f = a[i];
		}
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, x; cin >> n >> x;
	vector<int> a(n), pre(n), suf(n);
	for(int &i : a) cin >> i;

	lis(n, a, pre);
	reverse(a.begin(), a.end()); for(int &i : a) i = -i;
	lis(n, a, suf);
	reverse(a.begin(), a.end()); for(int &i : a) i = -i;
	reverse(suf.begin(), suf.end());

	// for(int i : a) cout << i << ' ';
	// cout nl;
	// for(int i : pre) cout << i << ' ';
	// cout nl;
	// for(int i : suf) cout << i << ' ';
	// cout nl;

	vector<array<int, 2>> b(n);
	vector<int> pos(n), suf1(n);
	for(int i=0; i<n; ++i) b[i] = {a[i], i};
	sort(b.begin(), b.end());
	for(int i=0; i<n; ++i) pos[b[i][1]] = i, suf1[i] = suf[b[i][1]];

	SegmentTree st(suf);
	int ans = 1;
	
	for(int i=0; i<n; ++i){
		st.update(pos[i], -1e18);
		array<int, 2> search = {a[i]-x, -1};
		int l = upper_bound(b.begin(), b.end(), search) - b.begin();
		if(l<n){
			ans = max(ans, pre[i] + st.get(l, n-1));
		}
	}
	cout << ans;
}

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