Submission #1126685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126685		TrieTr	Global Warming (CEOI18_glo)	C++20	100 / 100	157 ms	10688 KiB

glo

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

void local() {
    #define taskname ""
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
}

#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;}
template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;}

const int N = 1e6 + 5;

int n, a[N], lim, x;

int node[N << 1];
void update(int i, int v) {
    for(node[i += lim] = v, i >>= 1; i; i >>= 1) {
        node[i] = max(node[i << 1], node[i << 1 | 1]);
    }
}
int get(int l, int r) {
    int res = 0;
    for(l += lim, r += lim; l < r; l >>= 1, r >>= 1) {
        if(l & 1) maxi(res, node[l++]);
        if(r & 1) maxi(res, node[--r]);
    }
    return res;
}
int dp[N];
int main() {
    fastio; local();
    cin >> n >> x;
    vector<int> val;
    for(int i = 1; i <= n; i++) cin >> a[i];

    val.emplace_back(-2e9);
    for(int i = 1; i <= n; i++) val.emplace_back(a[i]);
    sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin()); lim = val.size();
    auto Rank = [&](int x) {
        return lower_bound(val.begin(), val.end(), x) - val.begin();
    };
    for(int i = 1; i <= n; i++) a[i] = Rank(a[i]);
    int res = 0;
    for(int i = 1; i <= n; i++) {
        dp[i] = get(1, a[i]) + 1;
        update(a[i], dp[i]);
        maxi(res, dp[i]);
    }
    memset(node, 0, sizeof(node));
    for(int i = n; i > 0; i--) {
        dp[i] = get(a[i] + 1, lim + 1) + 1;
        update(a[i], dp[i]);
        int p = Rank(val[a[i - 1]] - x + 1);
        maxi(res, dp[i - 1] + get(p, lim));
    }
    cout << res;
}

Compilation message (stderr)

glo.cpp: In function 'void local()':
glo.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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