Submission #384864

#	Time	Username	Problem	Language	Result	Execution time	Memory
384864		mariowong	Global Warming (CEOI18_glo)	C++14	100 / 100	500 ms	4708 KiB

glo

#include <bits/stdc++.h>

using namespace std;

int n,d,a[200005],now,ans_used[200005],ans[200005],anss,pt;
vector <pair<int,int>  > v1,v2;
void solve(int l,int r){
	if (l == r){
		ans[l]=max(ans[l],1);
		ans_used[l]=max(ans_used[l],1);
	}
	else
	{
		int mid=(l+r)/2;
		solve(l,mid);
		v1.clear(); v2.clear();
		for (int i=l;i<=mid;i++){
			v1.push_back(make_pair(a[i],ans_used[i]));
		}
		for (int i=mid+1;i<=r;i++){
			v2.push_back(make_pair(a[i],i));
		}
		sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end());
		pt=0; now=0;
		for (int i=0;i<v2.size();i++){
			while (pt < (int)v1.size() && v1[pt].first < v2[i].first){
				now=max(now,v1[pt].second);
				pt++;
			}
			ans_used[v2[i].second]=max(ans_used[v2[i].second],now+1);
		}
		v1.clear(); v2.clear();
		for (int i=l;i<=mid;i++){
			v1.push_back(make_pair(a[i],ans[i]));
		}
		for (int i=mid+1;i<=r;i++){
			v2.push_back(make_pair(a[i],i));
		}
		sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end());
		pt=0; now=0; 
		for (int i=0;i<v2.size();i++){
			while (pt < (int)v1.size() && v1[pt].first < v2[i].first){
				now=max(now,v1[pt].second);
				pt++;
			}
			ans[v2[i].second]=max(ans[v2[i].second],now+1);
		}
		pt=0; now=0;
		for (int i=0;i<v2.size();i++){
			while (pt < (int)v1.size() && v1[pt].first-d < v2[i].first){
				now=max(now,v1[pt].second);
				pt++;
			}
			ans_used[v2[i].second]=max(ans_used[v2[i].second],now+1);
		}
		solve(mid+1,r);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> d;
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}
	solve(1,n);
	for (int i=1;i<=n;i++){
		anss=max(anss,max(ans_used[i],ans[i]));
	}
	cout << anss << "\n";
	return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void solve(int, int)':
glo.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for (int i=0;i<v2.size();i++){
      |                ~^~~~~~~~~~
glo.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i=0;i<v2.size();i++){
      |                ~^~~~~~~~~~
glo.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i=0;i<v2.size();i++){
      |                ~^~~~~~~~~~

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