oj.uz

답안 #70987

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

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

struct Seg{
	int tree[1<<19];

	void upt(int v, int s, int e, int x, int val){
		if(x<s || e<x) return;
		if(s==e){ tree[v]=val; return; }
		upt(v*2,s,(s+e)/2,x,val);
		upt(v*2+1,(s+e)/2+1,e,x,val);
		tree[v]=max(tree[v*2],tree[v*2+1]);
	}
	void upt(int x, int v){
		upt(1,0,lim,x,v);
	}
	int mx(int v, int s, int e, int r){
		if(e<=r) return tree[v];
		int m=(s+e)/2;
		if(r<=m) return mx(v*2,s,m,r);
		else return max(mx(v*2,s,m,r), mx(v*2+1,m+1,e,r));
	}
	int mx(int r){
		return mx(1,0,lim,r);
	}
} S1, S2;

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]);
		S1.upt(p1, S1.mx(p1)+1);
	}
	cout<<S1.mx(lim)<<'\n';
/*	
	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 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 4204 KB Output is correct
2 Correct 192 ms 4204 KB Output is correct
3 Correct 188 ms 4204 KB Output is correct
4 Correct 191 ms 4204 KB Output is correct
5 Incorrect 78 ms 4204 KB Output isn't correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 4204 KB Output is correct
2 Correct 41 ms 4204 KB Output is correct
3 Correct 40 ms 4204 KB Output is correct
4 Incorrect 31 ms 4204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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