Submission #95188

#	Time	Username	Problem	Language	Result	Execution time	Memory
95188		Retro3014	Global Warming (CEOI18_glo)	C++17	100 / 100	73 ms	4712 KiB

glo

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;
#define MAX_N 200000


int N, D;
vector<int> v;
vector<int> stack;
int num[MAX_N+1];
int ans = 0;

int main(){
	scanf("%d %d", &N, &D);
	int x;
	for(int i=0; i<N; i++){
		scanf("%d", &x); v.push_back(x);
	}
	for(int i=v.size()-1; i>=0; i--){
		if(stack.empty()){
			num[i] = 1;
			stack.push_back(v[i]);
		}else{
			if(stack.back()>v[i]){
				stack.push_back(v[i]);
				num[i] = stack.size();
			}else{
				int s = 0, e = stack.size()-1, m;
				while(s<e){
					m = (s+e)/2;
					if(stack[m]>v[i])	s = m+1;
					else	e = m;
				}
				num[i] = s+1;
				stack[s] = v[i];
			}
		}
	}
	stack.clear();
	for(int i=0; i<v.size(); i++){
		int s = 0, e = stack.size(), m;
		while(s<e){
			m=(s+e)/2;
			if(stack[m]<v[i]+D) s = m+1;
			else	e = m;
		}
		//cout<<i<<" "<<s<<" "<<num[i]<<endl;
		ans = max(ans, s+num[i]);
		if(stack.empty()){
			stack.push_back(v[i]);
		}else{
			if(stack.back()<v[i])	stack.push_back(v[i]);
			else{
				s = 0; e = stack.size()-1;
				while(s<e){
					m = (s+e)/2;
					if(stack[m]<v[i])	s = m+1;
					else	e = m;
				}
				stack[s] = v[i];
			}
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
glo.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &D);
  ~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x); v.push_back(x);
   ~~~~~^~~~~~~~~~

• 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