oj.uz

Submission #1090622

# Submission time Handle Problem Language Result Execution time Memory
1090622 2024-09-18T14:19:08 Z Nurislam Global Warming (CEOI18_glo) C++17
10 / 100
 142 ms 12048 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;
int 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;
	N = n+5;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)cin >> a[i];
	
		vector<int> s;
		s = a;
		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);
	}
	
	
	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);
		chmax(ans, l + t.get(id(a[i]-x+1, 0), id(a[i]+x-1, 1)));
	}
	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 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 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 138 ms 11600 KB Output is correct
2 Correct 136 ms 11600 KB Output is correct
3 Correct 141 ms 11604 KB Output is correct
4 Correct 142 ms 11732 KB Output is correct
5 Correct 64 ms 11992 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3160 KB Output is correct
2 Correct 29 ms 3268 KB Output is correct
3 Correct 31 ms 3164 KB Output is correct
4 Incorrect 16 ms 3416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 5968 KB Output is correct
2 Correct 65 ms 5968 KB Output is correct
3 Correct 137 ms 11604 KB Output is correct
4 Incorrect 70 ms 12048 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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