Submission #320943

#	Time	Username	Problem	Language	Result	Execution time	Memory
320943		phathnv	Global Warming (CEOI18_glo)	C++11	100 / 100	96 ms	7012 KiB

glo

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "GlobalWarming"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 2e5 + 1;
const int INF = 1e9 + 10;

struct fenwickTree{
    int d[N];
    void update(int x, int val){
        for(; x < N; x += x & -x)
            d[x] = max(d[x], val);
    }
    int get(int x){
        int res = 0;
        for(; x > 0; x -= x & -x)
            res = max(res, d[x]);
        return res;
    }
} bit;

int n, x, a[N], l[N], r[N], dp[N], ind[N];

void readInput(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> x;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
}

void solve(){
    dp[0] = -INF;
    for(int i = 1; i <= n; i++)
        dp[i] = INF;
    for(int i = 1; i <= n; i++){
        l[i] = lower_bound(dp, dp + n + 1, a[i]) - dp;
        dp[l[i]] = min(dp[l[i]], a[i]);
    }

    dp[0] = INF;
    for(int i = 1; i <= n; i++)
        dp[i] = -INF;
    for(int i = n; i >= 1; i--){
        r[i] = lower_bound(dp, dp + n + 1, a[i], greater<int>()) - dp;
        dp[r[i]] = max(dp[r[i]], a[i]);
    }
    
    for(int i = 1; i <= n; i++)
        ind[i] = i;
    sort(ind + 1, ind + n + 1, [=](const int &x, const int &y){
            return a[x] < a[y];
         });
    int ptr = 1, res = 0;
    for(int i = 1; i <= n; i++){
        int pos = ind[i];
        while (ptr <= n && a[pos] + x > a[ind[ptr]]){
            bit.update(ind[ptr], l[ind[ptr]]);
            ptr++;
        }
        res = max(res, r[pos] + bit.get(pos - 1));
    }
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    solve();
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   77 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         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