# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95187 | Retro3014 | Global Warming (CEOI18_glo) | C++17 | 68 ms | 3984 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |