Submission #639793

#	Time	Username	Problem	Language	Result	Execution time	Memory
639793		a_aguilo	Global Warming (CEOI18_glo)	C++14	0 / 100	88 ms	1840 KiB

glo

#include<bits/stdc++.h>

using namespace std;

int n, x, HI;

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 = HI;
    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 lo;
}

int main(){
    cin >> n >> x;
    int V[n];
    int endWithLength[n];
    for(int i = 0; i < n; ++i) cin >> V[i];
    HI = 0;
    memset(endWithLength, 0, sizeof(endWithLength));
    endWithLength[0] = V[0];
    for(int i = 1; i < n; ++i){
        int pos = binarySearch((long long)V[i], endWithLength);
        if(pos == HI){
            if(V[i] >= endWithLength[pos]) pos++;
        }
        HI = max(HI, pos);
        //cout << "i " << i << " || value " << V[i] << " || pos1 " << pos;
        endWithLength[pos] = V[i];
        //print(endWithLength);
    }
    cout << HI+1 << endl;
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int binarySearch(int, int*)':
glo.cpp:14:9: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   14 |     int ans = 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