oj.uz

답안 #386746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386746 2021-04-07T09:13:21 Z Cantfindme Global Warming (CEOI18_glo) C++17
0 / 100
 445 ms 32108 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 32108 KB Output is correct
2 Correct 445 ms 31980 KB Output is correct
3 Correct 404 ms 31980 KB Output is correct
4 Correct 414 ms 31980 KB Output is correct
5 Incorrect 178 ms 32096 KB Output isn't correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 8428 KB Output is correct
2 Correct 85 ms 8300 KB Output is correct
3 Correct 83 ms 8428 KB Output is correct
4 Incorrect 40 ms 8424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 16364 KB Output is correct
2 Correct 159 ms 16236 KB Output is correct
3 Correct 356 ms 32108 KB Output is correct
4 Incorrect 155 ms 32096 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -