Submission #385778

#	Time	Username	Problem	Language	Result	Execution time	Memory
385778		SansPapyrus683	Global Warming (CEOI18_glo)	C++17	100 / 100	120 ms	3172 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;
/**
 * https://oj.uz/problem/view/CEOI18_glo
 * 8 10
 * 7 3 5 12 2 7 3 4 should output 5
 */
int main() {
    int temp_num;
    int max_cheating;
    std::cin >> temp_num >> max_cheating;
    vector<int> temps(temp_num);
    for (int t = 0; t < temp_num; t++) {
        std::cin >> temps[t];
    }
    
    vector<int> pref_longest(temp_num);
    vector<int> min_endings;
    for (int i = 0; i < temp_num; i++) {
        int t = temps[i];
		int pos = std::lower_bound(min_endings.begin(), min_endings.end(), t) - min_endings.begin();
		if (pos == min_endings.size()) {
            min_endings.push_back(t);
        } else {
            min_endings[pos] = t;
        }
        pref_longest[i] = pos + 1;
	}

    int longest = 0;
    vector<int> max_begins;
    for (int i = temp_num - 1; i >= 0; i--) {
        int t = temps[i];
        // negative to keep the binary search happy
        int pos = std::lower_bound(max_begins.begin(), max_begins.end(), -t) - max_begins.begin();
        longest = std::max(longest, pref_longest[i] + pos);
        
        int insert_pos = std::lower_bound(
            max_begins.begin(), max_begins.end(), -t - max_cheating
        ) - max_begins.begin();
        if (insert_pos == max_begins.size()) {
            max_begins.push_back(-t - max_cheating);
        } else {
            max_begins[insert_pos] = -t - max_cheating;
        }
    }
    cout << longest << endl;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:27:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if (pos == min_endings.size()) {
      |       ~~~~^~~~~~~~~~~~~~~~~~~~~
glo.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (insert_pos == max_begins.size()) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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