Submission #1089487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089487		DangKhoizzzz	Global Warming (CEOI18_glo)	C++14	100 / 100	121 ms	7336 KiB

glo

#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;
}

• 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