Submission #639791

#	Time	Username	Problem	Language	Result	Execution time	Memory
639791		a_aguilo	Global Warming (CEOI18_glo)	C++14	0 / 100	77 ms	2620 KiB

glo

#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;
}

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