제출 #639791

#제출 시각아이디문제언어결과실행 시간메모리
639791a_aguiloGlobal Warming (CEOI18_glo)C++14
0 / 100
77 ms2620 KiB
#include<bits/stdc++.h> using namespace std; int n, x, HI; long long binarySearch(long long int x, int arr[], int hi){ int lo = 0; int ans = 0; while(hi >= lo){ int mid = lo + (hi-lo)/2; if((long long)arr[mid] < x) { lo = mid+1; ans = mid; } else{ hi = mid-1; } } return ans; } int main(){ cin >> n >> x; int V[n]; int endWithLength[2][n]; for(int i = 0; i < n; ++i) cin >> V[i]; HI = 1; int HI2 = 1; memset(endWithLength, 0, sizeof(endWithLength)); endWithLength[0][0] = V[0]; endWithLength[1][0] = V[0]; for(int i = 1; i < n; ++i){ int pos = binarySearch((long long)V[i], endWithLength[0], HI); if(pos == HI){ HI++; } //cout << "i " << i << " value " << V[i] << " pos1 " << pos; endWithLength[0][pos] = V[i]; pos = binarySearch((long long)V[i]+x, endWithLength[0], HI); if(endWithLength[1][pos] != 0) endWithLength[1][pos] = min(endWithLength[1][pos], V[i]); else endWithLength[1][pos] = V[i]; HI2 = max(HI2, pos+1); //cout << " pos2 " << pos; pos = binarySearch((long long)V[i], endWithLength[1], HI2); endWithLength[1][pos] = V[i]; HI2 = max(HI2, pos+1); //cout << " pos3 " << pos << endl;; //cout << i << " " << V[i] << " " << pos; } cout << max(HI2, HI) << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...