Submission #639796

#	Time	Username	Problem	Language	Result	Execution time	Memory
639796		a_aguilo	Global Warming (CEOI18_glo)	C++14	0 / 100	89 ms	1832 KiB

glo

#include<bits/stdc++.h>

using namespace std;

int n, x;

void print(int v[]){
    for(int i = 0; i < n; ++i) cout << " " << v[i];
    cout << endl;
}

int binarySearch(int x, int arr[]){
    int lo = 0, hi = n;
    int ans = 0;
    while(hi >= lo){
        int mid = lo + (hi-lo)/2;
        if(arr[mid] <= x) {
            lo = mid+1;
            ans = mid;
        }
        else{
            hi = mid-1;
        }
    }
    return ans;
}

int main(){
    cin >> n >> x;
    int V[n];
    int endWithLength[n];
    for(int i = 0; i < n; ++i) cin >> V[i];
    memset(endWithLength, 1e9+1, sizeof(endWithLength));
    endWithLength[0] = V[0];
    int ans = 0;
    for(int i = 1; i < n; ++i){
        int pos = binarySearch((long long)V[i], endWithLength);
        //cout << "i " << i << " || value " << V[i] << " || pos1 " << pos;
        endWithLength[pos] = V[i];
        ans = max(ans, pos);
        //print(endWithLength);
    }
    cout << ans+1 << 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