Submission #868661

#	Time	Username	Problem	Language	Result	Execution time	Memory
868661		WLZ	Global Warming (CEOI18_glo)	C++17	100 / 100	49 ms	5388 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...) 0
#endif

constexpr int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, x; cin >> n >> x;

    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    vector<int> dp_l(n + 1, INF); dp_l[0] = -INF;
    vector<int> longest(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int j = lower_bound(dp_l.begin(), dp_l.end(), t[i]) - dp_l.begin();
        dp_l[j] = t[i];
        longest[i] = j;
        ans = max(ans, j);
        debug(dp_l);
    }
    debug(longest);

    vector<int> dp_r(n + 1, -INF); dp_r[0] = INF;
    for (int i = n - 1; i >= 0; i--) {
        int k = lower_bound(dp_r.begin(), dp_r.end(), t[i] - x, greater<>()) - dp_r.begin() - 1;
        ans = max(ans, longest[i] + k);
        debug(i, ans, k);

        int j = lower_bound(dp_r.begin(), dp_r.end(), t[i], greater<>()) - dp_r.begin();
        dp_r[j] = t[i];
        debug(dp_r);
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
glo.cpp:28:9: note: in expansion of macro 'debug'
   28 |         debug(dp_l);
      |         ^~~~~
glo.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
glo.cpp:30:5: note: in expansion of macro 'debug'
   30 |     debug(longest);
      |     ^~~~~
glo.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
glo.cpp:36:9: note: in expansion of macro 'debug'
   36 |         debug(i, ans, k);
      |         ^~~~~
glo.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
glo.cpp:40:9: note: in expansion of macro 'debug'
   40 |         debug(dp_r);
      |         ^~~~~

• 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