Submission #386746

#	Time	Username	Problem	Language	Result	Execution time	Memory
386746		Cantfindme	Global Warming (CEOI18_glo)	C++17	0 / 100	445 ms	32108 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;
 
const int maxn = 200010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7; 

int n, X;

struct node {
	int s,m,e,v;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		v = 0;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	
	void up(int x, int newv) {
		if (s == e) v = max(v,newv);
		else {
			if (x <= m) l -> up(x,newv);
			else r -> up(x,newv);
			v = max(l -> v, r -> v);
		}
	}
	
	int rmq(int x, int y) {
		if (x == s and e == y) return v;
		if (x > m) return r -> rmq(x,y);
		else if (y <= m) return l -> rmq(x,y);
		else return max(l -> rmq(x,m), r -> rmq(m+1,y));
	}
}*root;

int best[maxn];
int suf;

int32_t main() {
	//FAST
	
	cin >> n >> X;
	vector <int> v(n);
	for (int i =0;i<n;i++) {
		cin >> v[i];
	}
	
	vector <int> vv = v;
	sort(all(vv));
	
	root = new node(0,n-1);
	
	vector <int> lis;
	for (int i =0;i<n;i++) {
		int x = v[i];
		if (lis.empty() or x > lis.back()) {
			lis.push_back(x);
			best[i] = lis.size();
		} else {
			int pos = lower_bound(all(lis),x) - lis.begin();
			lis[pos] = x;
			best[i] = pos + 1;
		}
	}
	
	//cout << "HELLO";
	//for (int i =0;i<n;i++) cout << best[i] << " ";
	
	int rans = best[n-1];
	for (int i =n-1;i>=0;i--) {
		int p = upper_bound(all(vv),v[i] - X) - vv.begin();
		if (p <= n-1) suf = root -> rmq(p,n-1);
		else suf = 0;
		
		rans = max(rans, best[i] + suf);
		
		p = lower_bound(all(vv),v[i]) - vv.begin();
		if (p <= n-1) suf = root -> rmq(p,n-1);
		else suf = 0;
		root -> up(p,suf+1);
		
	}
	
	
	cout << rans;
}

• 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