Submission #580495

#	Time	Username	Problem	Language	Result	Execution time	Memory
580495		amunduzbaev	Global Warming (CEOI18_glo)	C++17	100 / 100	424 ms	16692 KiB

glo

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 4e5 + 5;
int a[N];

struct ST{
	int tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x << 1);
		else sett(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}tree;
int pref[N], suff[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, x; cin>>n>>x;
	vector<int> t;
	for(int i=0;i<n;i++){
		cin>>a[i];
		t.push_back(a[i]);
		t.push_back(a[i] - x);
	}
	
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	for(int i=0;i<n;i++){
		int p = lower_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
		pref[i] = tree.get(0, p - 1) + 1;
		tree.sett(p, pref[i]);
	}
	for(int i=0;i<N;i++) tree.sett(i, 0);
	
	for(int i=n-1;~i;i--){
		int p = upper_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
		int tmp = tree.get(p, N - 1);
		int p2 = upper_bound(t.begin(), t.end(), a[i] - x) - t.begin() + 1;
		suff[i] = tree.get(p2, N - 1);
		tree.sett(p - 1, tmp + 1);
	}
	
	int res = 0;
	for(int i=0;i<n;i++){
		res = max(res, pref[i] + suff[i]);
	}
	//~ for(int i=0;i<n;i++){
		//~ cout<<pref[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<suff[i]<<" ";
	//~ } cout<<"\n";
	
	cout<<res<<"\n";
}

• 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