Submission #384858

#	Time	Username	Problem	Language	Result	Execution time	Memory
384858		mariowong	Global Warming (CEOI18_glo)	C++14	48 / 100	804 ms	262148 KiB

glo

#include <bits/stdc++.h>

using namespace std;

int n,d,a[200005],now,ans,val1,val2,val3;
struct Node{
	int maxval;
	Node *l, *r;
	Node(): maxval(0),l(NULL),r(NULL) {}
};
void update(Node *u,int x,int y,int pos,int val){ 	
	if (x == y)
	u->maxval=max(u->maxval,val);
	else
	{
		int mid=(x+y)/2;
		if (u->l == NULL) u->l = new Node();
		if (u->r == NULL) u->r = new Node();
		if (pos <= mid) update(u->l,x,mid,pos,val);
		else update(u->r,mid+1,y,pos,val);
		u->maxval=max(u->l->maxval,u->r->maxval);
	}
}
int query(Node *u,int x,int y,int l,int r){
	if (l <= x && y <= r)
	return u->maxval;
	if (l > y || r < x)
	return 0;
	int mid=(x+y)/2;
	if (u->l != NULL && u->r != NULL)
	return max(query(u->l,x,mid,l,r),query(u->r,mid+1,y,l,r));
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> d;
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}
	Node *used_seg = new Node();
	Node *seg = new Node();
	for (int i=1;i<=n;i++){
		val1=query(seg,1,1e9+2,1,a[i]-1)+1; // not yet used decrase
		val2=query(seg,1,1e9+2,1,min((int)1e9+2,a[i]+d-1))+1;  //now use decrease
		val3=query(used_seg,1,1e9+2,1,a[i]-1)+1;  //used decrease
	//	cout << val1 << " " << val2 << " " << val3 << "\n";
		ans=max(ans,max(max(val1,val2),val3));
		update(seg,1,1e9+2,a[i],val1);
		update(used_seg,1,1e9+2,a[i],val2);
		update(used_seg,1,1e9+2,a[i],val3);
	//	solve(1,1,now);
	}
	cout << ans << "\n";
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25