oj.uz

Submission #1090638

# Submission time Handle Problem Language Result Execution time Memory
1090638 2024-09-18T14:43:29 Z Nurislam Global Warming (CEOI18_glo) C++17
10 / 100
 196 ms 13876 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long


template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int inf = 1e10, N = 2e5+5;
//int mod = 998244353
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
struct segtree{
	vector<int> t;
	segtree(){
		t.resize(N*4);
	};
	void upd(int ps, int val, int i = 1, int l = 1, int r = N){
		if(l == r){
			t[i] = val;
			return;
		}
		int m = (l+r)>>1;
		if(ps <= m)upd(ps, val, i*2, l, m);
		else upd(ps, val, i*2+1, m+1, r);
		t[i] = max(t[i*2], t[i*2+1]);
	};
	
	int get(int l, int r, int tl = 1, int tr = N, int i = 1){
		if(tl > r || tr < l || tl > tr)return 0;
		if(l <= tl && tr <= r)return t[i];
		int m = (tl+tr)>>1;
		return max(get(l, r, tl, m, i*2), get(l, r, m+1, tr, i*2+1));
	};
};

void solve(){
	int n, x;
	cin >> n >> x;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)cin >> a[i];
	vector<int> init = a;
		vector<int> s;
		s = a;s.pb(-inf);s.pb(inf);
		sort(all(s));
		s.erase(unique(all(s)), s.end());
		for(int &i:a)i = lower_bound(all(s), i) - s.begin();
		auto id = [&](int x, int t) -> int{
			int l = lower_bound(all(s), x)-s.begin();
			while(t == 0 && s[l] < x)l++;
			while(t == 1 && s[l] > x)l--;
			return l;
		};
		
		
	segtree t;
	vector<int> lis;lis.pb(0);
	for(int i = 1; i <= n; i++){
		int l = lower_bound(all(lis), a[i])-lis.begin();
		if(l == (int)lis.size())
			lis.pb(a[i]);
		else 
			lis[l] = a[i];
		t.upd(a[i], l);
		//cout << l << ' ';
	}
	
	//cout << '\n';
	
	int ans = lis.size() - 1;
	lis.clear();
	lis.pb(-inf);
	
	for(int i = n; i >= 1; i--){
		int l = lower_bound(all(lis), -a[i]) - lis.begin();
		if(l == (int)lis.size())
			lis.pb(-a[i]);
		else 
			lis[l] = -a[i];
		t.upd(a[i], 0);
		//cout << t.get(id(a[i]-x+1, 0), id(a[i]+x-1, 1)) << ' ';
		//cout << id(init[i]-x+1, 0) << ' ' << id(init[i]+x-1, 1) << '\n';
		//cout << init[i]-x+1 << ' ' << init[i]+x-1 << '\n';
		chmax(ans, l + t.get(id(init[i]-x, 0), id(init[i]+x, 1)));
	}
	//cout << '\n';
	cout << ans << '\n';
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Incorrect 2 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Incorrect 2 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Incorrect 2 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 12712 KB Output is correct
2 Correct 192 ms 12852 KB Output is correct
3 Correct 186 ms 12596 KB Output is correct
4 Correct 187 ms 12600 KB Output is correct
5 Correct 85 ms 13876 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8144 KB Output is correct
2 Correct 44 ms 8148 KB Output is correct
3 Correct 45 ms 8148 KB Output is correct
4 Incorrect 23 ms 8656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9796 KB Output is correct
2 Correct 68 ms 9668 KB Output is correct
3 Correct 153 ms 12600 KB Output is correct
4 Incorrect 85 ms 13876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Incorrect 2 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -