제출 #1023897

#제출 시각아이디문제언어결과실행 시간메모리
1023897vjudge1Global Warming (CEOI18_glo)C++14
100 / 100
107 ms7084 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int maxn = 4e5 + 7;

int n , x , a[maxn] , b[maxn];

struct Fenwick
{
	int bit[maxn];
	void update(int pos,int val)
	{
		for(;pos < maxn;pos += pos & -pos)bit[pos] = max(bit[pos],val);
	}
	int get(int pos)
	{
		int res = 0;
		for(;pos > 0;pos -= pos & -pos)res = max(res,bit[pos]);
		return res;
	}
};

Fenwick sta , stb;



void compress()
{
    vector <int> order;
    for(int i = 1; i <= n; i++)
    {
        order.push_back(a[i]);
        order.push_back(a[i] - x);
    }
    sort(order.begin() , order.end());
    order.erase(unique(order.begin(),order.end()),order.end());
    for(int i = 1; i <= n; i++)
    {
        b[i] = lower_bound(order.begin() , order.end() , a[i] - x) - order.begin() + 1;
        a[i] = lower_bound(order.begin() , order.end() , a[i]) - order.begin() + 1;
    }
}

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

    compress();

    //for(int i = 1; i <= n; i++) cout << a[i] << ' '; cout << '\n';
    //for(int i = 1; i <= n; i++) cout << b[i] << ' '; cout << '\n';

    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        // b[i] = a[i] - x
        int geta1 = sta.get(b[i] - 1); // lay nhung thg a[i] - x
        ans = max(ans , geta1 + 1);
        int getb2 = stb.get(a[i] - 1);// lay a[i]
        int geta2 = sta.get(a[i] - 1); // lay nhung thg a[i] - x

        ans = max(ans , max(getb2 , geta2) + 1);

        //cout << geta1 << ' ' << geta2 << ' ' << getb2 << '\n';

        stb.update(a[i] , max(getb2 , geta2) + 1);
        sta.update(b[i] , geta1 + 1);
    }
    cout << ans << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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...