Submission #1304606

#TimeUsernameProblemLanguageResultExecution timeMemory
1304606thaibaotran555Global Warming (CEOI18_glo)C++20
15 / 100
40 ms6736 KiB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define maxN 400007

struct SEG
{
    int st[maxN*4] = {0};
    void update(int id, int l, int r, int pos, int val)
    {
        if(l==r)
        {
            st[id] = val;
            return;
        }
        int mid = (l+r)/2;
        if(pos <= mid)
            update(id*2, l, mid, pos, val);
        else update(id*2+1, mid+1, r, pos, val);
        st[id] = max(st[id*2+1], st[id*2]);
    }
    int query(int id, int l, int r, int u, int v)
    {
        if(u > v)
            return 0;
        if(l > v || u > r)
            return 0;
        if(u <= l && r <= v)
            return st[id];
        int mid = (l+r)/2;
        int ans1 = query(id*2, l, mid, u, v);
        int ans2 = query(id*2+1, mid+1, r, u, v);
        return max(ans1, ans2);
    }
    void del()
    {
        memset(st, 0, sizeof(st));
    }
};

vector<int>val;
int n, x, m;
int a[maxN];
int pos[maxN] = {0};
int dp1[maxN]; //normal LIS
int dp2[maxN]; //end+x
int dp3[maxN]; //rev LIS
SEG seg;

void readData()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        val.push_back(a[i]);
        val.push_back(a[i]+x);
    }
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    m = val.size();
    for(int i = 0; i < m; i++)
        pos[val[i]] = i+1;
}

void solve()
{
    for(int i = 1; i <= n; i++)
    {
        dp1[i] = seg.query(1, 1, m, 1, pos[a[i]]-1)+1;
        dp2[i] = seg.query(1, 1, m, 1, pos[a[i]+x]-1)+1;
        seg.update(1, 1, m, pos[a[i]], dp1[i]);
    }
    seg.del();
    for(int i = n; i >= 1; i--)
    {
        dp3[i] = seg.query(1, 1, m, pos[a[i]]+1, m)+1;
        seg.update(1, 1, m, pos[a[i]], dp3[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, dp2[i] + dp3[i] - 1);
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    readData();
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...