oj.uz

답안 #70984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70984 2018-08-24T00:55:15 Z 노영훈(#2202) Global Warming (CEOI18_glo) C++11
0 / 100
 178 ms 3808 KB 
#include <bits/stdc++.h>
using namespace std;
const int MX=200010, inf=2e9+1;

int n, A[MX], x, lim;
int tree[2][MX];
vector<int> X={-inf};

void upt(int T[], int x, int v){
	for(; 0<x && x<=lim; x+=x&(-x)) T[x]=max(T[x], v);
}
int mx(int T[], int r){
	int res=0;
	for(; r>0; r-=r&(-r)) res=max(res, T[r]);
	return res;
}

int find(int x){
	return upper_bound(X.begin(), X.end(), x)-X.begin()-1;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>x;
	for(int i=1; i<=n; i++) cin>>A[i], X.push_back(A[i]);
	sort(X.begin(), X.end());
	lim=unique(X.begin(), X.end())-X.begin();
	X.resize(lim); lim--;
	
	for(int i=1; i<=n; i++){
		int p1=find(A[i]), p2=find(A[i]+x-1);
		int a=mx(tree[0], p1), b=mx(tree[1], p1), c=mx(tree[0], p2);
		upt(tree[0], p1, a+1);
		upt(tree[1], p1, b+1);
		upt(tree[1], p1, c+1);
	}
	cout<<mx(tree[1], lim)<<'\n';
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 3700 KB Output is correct
2 Correct 170 ms 3700 KB Output is correct
3 Correct 156 ms 3700 KB Output is correct
4 Correct 176 ms 3792 KB Output is correct
5 Incorrect 92 ms 3792 KB Output isn't correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 3792 KB Output is correct
2 Correct 32 ms 3792 KB Output is correct
3 Correct 33 ms 3792 KB Output is correct
4 Incorrect 21 ms 3792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 3792 KB Output is correct
2 Correct 69 ms 3792 KB Output is correct
3 Correct 162 ms 3808 KB Output is correct
4 Incorrect 79 ms 3808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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