제출 #714821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714821		thimote75	Global Warming (CEOI18_glo)	C++14	0 / 100	2074 ms	212 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#define num long long

// LIS maintainer
struct LISm {
    map<num, num> d;

    void insert (num id, num res) {
        if (query(id) >= res) return ;
        if (d.find(id) != d.end())
            d.erase(id);

        d.insert({ id, res });

        auto it = d.find(id);
        while (it != d.end()) {
            it ++;
            if ((*it).second > res) break ;

            d.erase((*it).first);
            it = d.find(id);
        }
    }

    // returns the second value of the last iterator such that key < x
    num query (num x) {
        auto it = d.lower_bound(x); // first iterator such that key >= x
        if (it == d.begin()) return 0;
        it --; // last iterator such that key < x

        return (*it).second;
    }
    void show () {
        for (auto u : d)
            printf("%lld->%lld ", u.first, u.second);
        printf("\n");
    }
};

int main () {
    LISm lis_0;
    LISm lis_x;

    int nbTemp; num maxDelta;
    cin >> nbTemp >> maxDelta;

    num result = 0;

    for (int idTemp = 0; idTemp < nbTemp; idTemp ++) {
        num temp;
        cin >> temp;
        num temp_x = temp + maxDelta;

        num lis_0_value = 1 + lis_0.query(temp);
        //num lis_x_value = 1 + max( lis_0.query(temp_x), lis_x.query(temp_x) );

        //printf("\n--- %d %lld ---\n", idTemp, temp);
        //printf("%d: 0(%lld) +x(%lld)\n", idTemp, lis_0_value, lis_x_value);

        lis_0.insert( temp,   lis_0_value );
        //lis_0.show();
        //lis_x.insert( temp_x, lis_x_value );
        //lis_x.show();
    
        result = max(result, lis_0_value);
        //result = max(result, lis_x_value);
    }

    cout << result;
}

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int main()':
glo.cpp:56:13: warning: unused variable 'temp_x' [-Wunused-variable]
   56 |         num temp_x = temp + maxDelta;
      |             ^~~~~~

• 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