oj.uz

Submission #95187

# Submission time Handle Problem Language Result Execution time Memory
95187 2019-01-28T11:16:00 Z Retro3014 Global Warming (CEOI18_glo) C++17
10 / 100
 68 ms 3984 KB 
#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()-1, m;
		while(s<e){
			m=(s+e)/2;
			if(stack[m]<v[i]+D) s = m+1;
			else	e = m;
		}
		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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3984 KB Output is correct
2 Correct 67 ms 3848 KB Output is correct
3 Correct 67 ms 3944 KB Output is correct
4 Correct 67 ms 3948 KB Output is correct
5 Correct 36 ms 3944 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1268 KB Output is correct
2 Correct 17 ms 1268 KB Output is correct
3 Correct 17 ms 1264 KB Output is correct
4 Incorrect 10 ms 1140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 2172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -