oj.uz

Submission #1085616

# Submission time Handle Problem Language Result Execution time Memory
1085616 2024-09-08T13:33:31 Z vjudge1 Global Warming (CEOI18_glo) C++17
10 / 100
 25 ms 3164 KB 
#include <iostream>
#include <vector>
using namespace std;

int lengthOfLIS(vector<int>& nums)
{

    // Binary search approach
    int n = nums.size();
    vector<int> ans;

    // Initialize the answer vector with the
    // first element of nums
    ans.push_back(nums[0]);

    for (int i = 1; i < n; i++) {
        if (nums[i] > ans.back()) {

            // If the current number is greater
            // than the last element of the answer
            // vector, it means we have found a
            // longer increasing subsequence.
            // Hence, we append the current number
            // to the answer vector.
            ans.push_back(nums[i]);
        }
        else {

            // If the current number is not
            // greater than the last element of
            // the answer vector, we perform
            // a binary search to find the smallest
            // element in the answer vector that
            // is greater than or equal to the
            // current number.

            // The lower_bound function returns
            // an iterator pointing to the first
            // element that is not less than
            // the current number.
            int low = lower_bound(ans.begin(), ans.end(),
                                  nums[i])
                      - ans.begin();

            // We update the element at the
            // found position with the current number.
            // By doing this, we are maintaining
            // a sorted order in the answer vector.
            ans[low] = nums[i];
        }
    }

    // The length of the answer vector
    // represents the length of the
    // longest increasing subsequence.
    return ans.size();
}

// Thanks GFG

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, x;
	cin >> n >> x;
	vector <int> arr(n);
	for (int &i : arr) cin >> i;
	cout << lengthOfLIS(arr);
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3164 KB Output is correct
2 Correct 24 ms 3160 KB Output is correct
3 Correct 25 ms 3156 KB Output is correct
4 Correct 24 ms 3164 KB Output is correct
5 Correct 13 ms 3036 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1116 KB Output is correct
2 Correct 6 ms 1032 KB Output is correct
3 Correct 6 ms 1116 KB Output is correct
4 Incorrect 3 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -