oj.uz

답안 #70988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70988 2018-08-24T01:10:03 Z 노영훈(#2202) Global Warming (CEOI18_glo) C++11
10 / 100
 218 ms 4352 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);
	}
	int val(int v, int s, int e, int x){
		if(x<s || e<x) return 0;
		if(s==e) return tree[v];
		return max(val(v*2,s,(s+e)/2,x), val(v*2+1,(s+e)/2+1,e,x));
	}
} 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]-1);
		S1.upt(find(A[i]), S1.mx(p1)+1);
//		for(int j=1; j<=n; j++) cout<<S1.val(1,0,lim,find(A[j]))<<' ';
//		cout<<'\n';
	}
	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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 4292 KB Output is correct
2 Correct 200 ms 4352 KB Output is correct
3 Correct 218 ms 4352 KB Output is correct
4 Correct 201 ms 4352 KB Output is correct
5 Correct 81 ms 4352 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 4352 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 -